Mathematical Induction

Induction is a method of proving certain theorems. The idea is a bit sophisticated but in essence it is simple. In the following the reasoning is complete and logic is correct. Good old solid mathematics.

The easiest way to visualize it is a very long (endless) row of dominoes standing upright one after another. If a domino tips and falls it knocks down the next one too, and that knocks down the next. Then should I knock over the first one there is an endless chain-reaction and all of them fall, one after the other.

The method of induction is:

1. Show the relation is true for n = 1
2. Assuming the relation holds for n = m show that it holds for n = m + 1

As an application I propose to briefly prove a formula for an arithmetical series. This is a standard exercise.

-

Prove the formula: S (n) = 1 + 2 + 3 … + n = ½ n(n + 1)

First assume that this formula holds for n = k, i.e. assume the equation is true for an integer k.

Using this, if I take the next number n = k+1, I must show that

S (k+1) = 1 + 2 + 3 … + k + (k+1) = ½ (k+1) ( (k+1) + 1 )

LHS = S (k+1) = [ S (k) ] + (k+1)

= [ 1 + 2 + 3 + … + k ] + (k+1)
 

= [ ½ k (k+1) ] + (k+1)

= ½ k² + ½ k + k + 1
= ½ (k + 1) (k + 2) = RHS

The formula holds for n = 1 because ½·1·(1+1) = 1.

By the principle of mathematical induction we conclude that our formula holds for every positive integer n. The first domino is the case n = 1, and if any domino is named k, the next one would be k+1.

We could also picture the method as a ladder. If I can begin with the first rung and assume I can step for every rung k, to the next, k+1. It means in principle I can climb as high as I want and will eventually reach every integer n.

-

This kind of application is commonplace we learn it already in secondary school. There are very advanced and sophisticated theorems that can be proved with induction. It is an indispensable tool. The point is that the proof of such a result in fact consists of infinitely many lesser theorems. That is, the truth for n = k implies the truth of n = (k+1).

The amusing thing is that one has to have the answer before you can prove it! The formula may routinely be proved as correct with mathematical induction and if so the series established as convergent. In a way it is necessary for you know the answer before the question! Like in the Douglas Adams books. A question of reverse engineering.

Is it then one result, or infinitely many? Even if you might say that as such it is only one theorem, still in my opinion the academic knowledge comprising the total of all possible provable truths is unlimited.