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

Mohammed Iqbal R
Sep 3, 2018 · 3 min read

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 true

So 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 true

As 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.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade