Mathematical Induction

MATHEMATICAL INDUCTION:

Mathematical induction is a unique and special way to prove the things, in only two steps.

Step 1. Show that it is true for n = 1.
Step 2. Show that if n = k is true then n = k+1 is also true.

For example:

Prob. By principal of mathematical induction prove that
11n+2 + 122n+1 is divisible by 133, n ∈ N.

Solution.
Step 1 P(1)- Show it is true for n = 1
11n+2 + 122n+1 = 111+2 + 122(1)+1 = 1331 + 1728 = 3059

Yes 3059 is divisible by 133.
111+2 + 122(1)+1  is true.

Step 2 P(k)- Assume it is true for n = k

11k+2 + 122(k)+1  is true.
(above line is an assumption only, which we will use as a fact in rest of the solution)

Now, prove that 11(k+1)+2 + 122(k+1)+1 is divisible by 133. (here n = k +1 now, P(k+1))
We have,
P(k+1)

11(k+1)+2 + 122(k+1)+1 = 11k+3 + 122k+3

11(k+1)+2 + 122(k+1)+1 = 11k+2 x 11 + 122k+1x 122

11(k+1)+2 + 122(k+1)+1 = (11k+2 x 11) + (122k+1x 144 )

11(k+1)+2 + 122(k+1)+1 = (11k+2 x 11) + (122k+1x (11 + 133))

11(k+1)+2 + 122(k+1)+1 = (11k+2+ 122k+1)x 11+(122n+1 x 133)

11(k+1)+2 + 122(k+1)+1 = ((11k+2+122k+1)x 11)+(122n+1 x 133)

Here 11k+2+122k+1 is divisible by 133 as assumed in n = k, P(1),

And 122n+1 x 133 is multiple of 133 so it is divisible by 133.

So,

11(k+1)+2 + 122(k+1)+1 = ((divisible by 133)x 11)+(divisible by 133)

11(k+1)+2 + 122(k+1)+1 = divisible by 133.

In this problem

If n = n, i.e, P(1) is true then n = n+1, i.e, P(n+1) is also true. Hence proved.

Problems based on above study:

Prob. Prove the following proposition
12 + 22 + 32 +...........+ n2  = (n (n+1)(2n+1) ) /6.

Prob. By principal of mathematical induction prove that
11n+2 + 122n+! is divisible by 133, n ∈ N.

Prob. By mathematical induction prove that for any integer n,  11n+2 + 122n+1 is divisible by 133.

Prob. Show that 2 + 4 + 6 + …… + 2n = n (n+1) by mathematical induction.

Prob. Prove by induction that the sum of the cubes of three consecutive integers is divisible by 9.

Prob. Prove by mathematical induction that n2 + n is an even number for all natural numbers, n ≥ 1.

Prob. Prove by using method of induction-
12 + 22 + 32 +.......+ (3n - 2)2 = (n(6n2 - 3n -1)) /2.

Prob. Prove by mathematical induction -

12 - 22 + 32 -............+ (-1)n+1n2 = ((-1)n+1n(n+1)) /2.

Discrete Structure

EasyExamNotes.com covered following topics in these notes.
A list of Video lectures