Assignment 4 Of MTH202 solution Fall 2010

[Xpert]

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