Mth202 Assignment No. 4 Solution

Assignment 4 Of MTH202 (Fall 2010)

Maximum Marks: 15

Due Date: January 11, 2011

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?

Q:2

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

Q:3

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

Question#2 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


Question 3; Marks: 03
Use the Euclidean algorithm to find gcd (1331, 1001)
Solution
gcd(1331, 1001) = gcd(1001, 330)
= gcd(330, 11)
= gcd(11, 0)
= 11


How many bit strings of length 10 have

a) Exactly three 0’s?

is ka answer hai 10C3 =120

b) The same number of 0’s as 1’s?
is ka answer hai 10 C 5 = 152