Mth202 Assignment No. 4 Solution
Tuesday, January 11, 2011 Posted In Mth Edit ThisAssignment 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, x2n-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
