MTH-202-Assignment#04

MTH 202 Assignment #4 Solution:

 

Q-1:

How many bit strings of length 10 have

a)      Exactly three 0’s?

b)      The same number of 0’s as 1’s

 

 

Solution:

a) Exactly three 0’s?

Answer            10C3 =120

b) The same number of 0’s as 1’s?

Answer            10 C 5 = 152

 

Q-2

Prove by mathematical induction that for all positive integral values of n, x²ⁿ-1 is divisible by x +1 ;( x¹1) 

 

Solution:

using mathematical induction

step 1: first we will prove that for n =1 it is true

thus x^2n-1 = x^2-1 = (x-1)*(x+1) 

clearly since it has factor of x+1 we can say that x^2n-1 is divisible by x-1

step 2: let assume that for n = k it is true thus

x^2k-1 is divisible by x+1

thus we can write as x^2k-1 = P (x+1) P is quotient

now we have to prove that it is true for n=k+1

step 3: now let n = k+1 thus

x^2(k+1) - 1 = x^(2k+2) - 1 = x^2k*x^2 -1 = (x^2k-1+1)x^2 - 1

(x^2k-1)*x^2 + (x^2-1)

for step 2 we can write above equation as

P (x+1)*x^2 + (x+1)*(x-1) = (x+1)* (Px^2+x-1)

which contain factor of x+1 thus divisible by x+1

thus even it is proved for n=k+1

according to mathematical induction given is true for all integral values of n

 

Q:3

Use the Euclidean algorithm to find gcd (1331, 1001)

 

Solution:
gcd(1331, 1001) = gcd(1001, 330)
= gcd(330, 11)
= gcd(11, 0)
= 11