# 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 that11n+2 + 122n+1 is divisible by 133, n ∈ N.
Solution.Step 1 P(1)- Show it is true for n = 111n+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.