Question Bank

Mod 2 (Mathematical Induction)

Question Bank

Mod 2 (Mathematical Induction)

Question Bank

Mod 2 (Mathematical Induction)

Question Bank

Mod 2 (Mathematical Induction)

Q.1. Prove that the sum of the first n natural numbers is given

1+2+3+…+n= .

Answer:

Step 1:- Put n=K

Step 2:- Put n= K+1

Add (K+1) terms to put side of equation 1

Now equation 1 and 3 are equal

Now put n=1 we have equation 1

Q.2.Prove that Sum of a geometric sequence for any real number r except one and any integer

Answer:

Suppose r is a particular but arbitrarily chosen real number that is not equal to 1 and let the property be the equation.

We must shown that is true for all integers

By mathematical induction on n show that P(0) is true

Also because r' = r and r+1

Hence P(0) is true.

Q.3. Show that all integers K 0 if P(K) is true then P(K+1) is also true.

Answer:

Let K be any integer with K 0

We must show that P(K+1) is true i.e.

Or equivalently that

We will show that left hand rule of P(K+1) equals the right hand side.

The left-hand rule of P(K+1) is

By multiplying out and using the fact that

Q.4. Prove that the sum of consecutive cubes is equal to the square of the sum of first “n numbers.”

Answer:

Step 1:- put n=K

Step 2: Put n= K +1

Step 3: Add to both sides of equation

So equation 1 and 3 are equal

Now put n=1 in equation 1

The formula is true for every natural number.

Q.5. Use mathematical induction to prove well ordering principle of integers.

Answer:

 Let P(n) be the statement “Any non empty subset of integers having n number of elements has the least element.”

1)     P(1) is true because any subset of positive integers N, having just one element obviously has the least element.

2)     Assume that, for any m, every subset of N having K elements, K < m has the least elements.

3)     We will now prove that any subset of N having m elements has the least element.

Let

Where are positive integer

Consider

Then S' is a subset of N having (m-1) elements.

Since (m-1) < m, defer applying induction hypothesis to S', we know that S' has least element say 1.

Then min is the least element of S.

Thus, we have proved that S also has the least element.

Q.6. Prove Existence and uniqueness of binary integer representation.

Given any positive integer n, n has a unique representation in the form

Where r is a non negative integer, or 0 for all j= 0, 1, 2…r-1

Answer:

Let r=0, and and so n=1 can be written in in equation form.

Show that for all integers K 1 if P(1) is true for all integers i from 1 through K then P(K+1) is also true.

Let K be an integer with K 1

Where r is a non negative integer and y=1 or '0' for all j=0,1,2,…r – 1

Case 1:- (K+1) is even.

In this case is an integer and by inductive hypothesis since

Then

Where r is a non negative integer.

or 0 for all j=0,1,2,…r-1

Multiplying both sides of equation by 2 gives

K+1 =

Which gives a sum of power of 2.

Case 2:- (K+1) is odd.

In this case is an integer and by induction hypothesis since then,

Multiplying both side of equation by 2 and add 1

Which is also sum of power of 2 of required form.

Q.7. Prove that for any given integer n and any positive integer d, there exist unique integers q and r such that

Answer:

Let S be the set of all non negative integers of the form

n- d K

Where K is an integer. This set has at least one element.

And so (n – 0.d) is in s and if n is negative then

Since d is a positive integer and so (n – n d) is in S.

Some specific integers K=q

Adding dq to both sides gives

If r d then

And so on would be non negative integer in S that would be smaller than r.

But r is the smaller integer in S. This contradiction shows that the superposition r d must be false.

The preceding arguments prove that there exist integer r and q for which

Q.8. Prove that any positive integer n>1 can be written as a product of primes using strong mathematical induction.

Answer:

P(n) be the statement. Every positive integer n>1 can be written as a product of primes.

Let n=2 and 2=2 (because 2 is itself prime)

P(2) is true.

Let us assume that assertion hold for n=K+1.

i.e. to prove that n=K+1 written as a product of primes.

Therefore there are two cases.

Case i) (K+1) is prime

Therefore (K+1) = (K+1) [because K + 1 is prime]

Therefore P(K+1) is true in this case.

Case ii) (K+1) is a complete number

(K+1) = l. m (l, m )(

By induction assumption on integer l and m can be written as a product of primes l, m <K

P(l), P(m) is true.

Therefore (K+1) = (prime factors of l) × (prime factor of m)

= Product of primes

Therefore (K+1) is written as a product of primes.

P(K+1) is true in this case.

By case (i) and case (ii) P(K+1) is true. Therefore by strong mathematical Induction result is true for all positive integers.

Q.9. Prove Euclidean theorem.

Answer:

The Euclidean algorithm is supposed to take integers A and B with A> B 0 and compute their greatest common divisor.

Precondition: - A and B are integers with A>B 0. a=A, b=B and r=B.

While ( b≠0)

1)     r = a mod b

2)     a : =b

3)     b : r

End while

Post condition:- a = gcd (A,B)

Proof:

To prove the correctness of the loop, let the invariant be

The good of while loop is

G : b≠0

1)     Basic property: - I(0) is true before the first iteration of the loop.

According to precondition

a = A, b = B, r = B ,  0 B A

Hence

b = B and a = A then 0 b a

Hence I(0) is true.

Q.10. Using interactive methods of the following recurrence relation

Answer:

Given,

By interactive substitution we get

For i=n

Is required solution.

Q.11. Solve the following recurrence relation

Subject to initial condition

Answer:

Let us write the recurrence

The characteristic polynomial is

Solving we get

By initial condition we get

Solving we get

The solution is

Q.12. Prove that divisible by 6, for each integer n

Answer:

Let P(n) be -1 is divisible by 6,

i.e. P(n) : is an integer,

Let n=0

P(0) = is an integer.

P(0) is true.

Let n=1

is an integer.

P(1) is true

Assume that the result is true for n=K

i.e. is an integer.

i.e.

We have to prove that result from n= K +1

i.e. to prove the result for

Consider

m is an integer

(7m + 1) is an integer.

P(K + 1) is true

Therefore by induction

is divisible by

Q.13. Solve the following recurrence relation subject to initial condition

Answer:

 First let us assume the recurrence

Characteristic polynomial is

Roots are therefore with multiplicity 2, the general solution, therefore is

By initial conditions we get

Solving these three equation we get

Solution is

Q.14. Prove that n!+2 is divisible by 2 for all integers n 2.

Answer:

Let P(n) be (n! +2) is divisible by 2 for all integers n 2

i.e.  P(n) be is an integer

Let n=2

n! +2 =2! +2 =4

= is an integer

P(2) is true.

Assume the result for n = K, i.e. m where m is an integer

Therefore K! + 2 = 2m

Now we have to prove that result for n = K+1

i.e. to prove is an integer

Consider,

K, m is an integer.

(K+1)(m-1)+1 is also an integer.

is an integer.

P(K+1) is true.

By mathematical induction

(n! +2) is divisible by 2, for all integers n 2