The Simple Idea Behind Mathematical Induction

Consider this statement: 

Conjecture 

The sum of the first n odd natural numbers equals $n^2$. 

The following table illustrates what this conjecture says. Each row is headed by a natural number $n$, followed by the sum of the first n odd natural numbers, followed by $n^2$.

Note that in the first five lines of the table, the sum of the first n odd numbers really does add up to $n^2$. Notice also that these first five lines indicate that the nth odd natural number (the last number in each sum) is $2n − 1$. (For instance, when $n = 2$, the second odd natural number is $2·2−1 = 3$; when $n = 3$, the third odd natural number is $2·3−1 = 5$, etc.) 

The table raises a question. 

Does the sum 

$1+3+5+7+···+(2n−1)$ 

really always equal $n^2$ ? 

In other words, is the conjecture true? 

Let’s rephrase this. For each natural number $n$ (i.e., for each line of the table), we have a statement Sn, as follows:

$S_1 : 1 = 1^2$ 

$S_2 : 1+3 = 2^2$ 

$S_3 : 1+3+5 = 3^2$ 

. . . 

$S_n : 1+3+5+7+··· +(2n−1) = n^2$ 

Our question is: 

Are all of these statements true? 

Mathematical induction answers just this kind of question, where we have an infinite list of statements $S_1, S_2, S_3, ...$ that we want to prove true. 

The method is really quite simple. To visualize it, think of the statements as dominoes, lined up in a row. Suppose you can prove the first statement $S_1$, and symbolize this as domino $S_1$ being knocked down. 

Also, say you can prove that any statement $S_k$ being true (falling) forces the next statement $S_{k+1}$ to be true (to fall). 

Then $S_1$ falls, knocking down $S_2$. Next $S_2$ falls, knocking down $S_3$, then $S_3$ knocks down $S_4$, and so on. The inescapable conclusion is that all the statements are knocked down (proved true).