Mathematical Induction for the Non-math and the non-geek.

The sum of first n natural numbers is a very famous result in Mathematics.
If we name the above above statement as P(n), we can observe that,
P(1) : 1 = (1*2)/2 = 1 is true
P(2) : 1+2 = (2*3)/2 = 3 is true
P(3) : 1+2+3 = (3*4)/2 = 6 is trueSo can we conclude that P(n) is true for all natural numbers n ?
Fortunately, this is not how math works. Just because P(1) is true, P(2) is true and P(3) is true, we can’t really say P(n) is true for all natural numbers n. The best counter example is the below statement.
“S(n) : 2n+1 is a prime”
"S(1) : 3 is prime", which is true
"S(2) : 5 is prime", which is true
"S(3) : 7 is prime", which is trueAs soon as we put n=4, the above statement ceases to be true. So disproving a statement is very easy by giving a case that doesn’t work, however to prove a statement it is not sufficient to show that it works for a few cases.
The Motivation
Luckily in mathematics we have something called the Principle of Mathematical Induction (PMI). Imagine that there are few bicycles lined up in a row and the crazy me wants to kick and make them all fall down. How do I go about it ? Do I go and kick each and every cycle in the row ? No. Here’s what I would do.
a) Kick the very first bicycle and make it fall down.
b) Make sure that whenever a bicycle falls down, it will go and hit its successor and make it fall down.
This way I will make sure that all the bicycles would fall down to the ground. This is the underlying principle used in the PMI.
The Principle of Mathematical Induction
To prove that a statement P(n) is true for all natural numbers n, I just need to do the following :
a) Prove that P(1) is true.
b) Whenever P(k) is true for some n=k, it should lead to the truth of P(k+1).
Back to the Original Problem
a) We just saw that P(1) is true.
b) Now assume P(k) is true i.e.,
Now the LHS of P(k+1) is
Using (1), it can be written as,
So we just proved that P(k+1) is true using the truth of P(k). To conclude,
P(n) is true for all natural numbers n.