Mathematical induction is a very subtle proofing method.

Intuitively, natural numbers are numbers of the form:

1, 2 = 1 + 1, 3 = 2 + 1 = (1 + 1) + 1, ...

and so on infinitely.

To prove that a property holds for all natural numbers it is sufficient to show that

• it holds for the number 1; and that

• when it holds for a natural number n, then it also holds for its successor, i.e., n + 1.

This method is called Mathematical Induction.

Sum of the first n odd numbers

Adding odd numbers, you can notice a pattern.

• 1 = 1 = 1²

• 1 + 3 = 4 = 2²

• 1 + 3 + 5 = 9 = 3²

• 1 + 3 + 5 + 7 = 16 = 4²

• 1 + 3 + 5 + 7 + 9 = 25 = 5²

• 1 + 3 + 5 + 7 + 9 + 11 = 36 = 6²

It seems that the sum of the first n odd numbers is always equal to n². Well, it is impossible to test this property for all natural numbers, as they are infinite. But it is possible to prove it by induction, i.e., by showing that (i) and (ii) hold.

Note that (i) is valid, since 1 = 1². Suppose now that, for some natural n,

1 + 3 + 5 + 7 + 9 + ... + (2n − 1) = n²

is true. Adding 2n + 1, which is the next odd number after 2n − 1, to both sides of the above equality, we obtain the equality (also true):

1 + 3 + ... + (2n − 1) + (2n + 1) = n² + 2n + 1

Since n² + 2n + 1 = (n + 1)², we have:

1 + 3 + ... + (2n − 1) + (2n + 1) = (n + 1)²

This shows that the property is true for n + 1 every time that it is true for n (ii). Therefore, by induction, it is valid for every natural number n.

The logical basis

It might seem, in the demonstration above, that we are assuming the property is true for n in order to deduce that it is true for n + 1, and then concluding that it is always true, that is, that we are using the thesis to prove the theorem. But that is not the case. In fact, this is the most subtle aspect of this method. Given a natural number n, there are two possibilities:

• The property is true; or

• The property is false.

Hypothesis (ii) of the method does not require us to assume that the property is true for all natural numbers n. It may, eventually, be false for some values of n, or even for all values of n. What hypothesis (ii) requires is that whenever some n belongs to category (a) above, then n + 1 also belongs to that same category; requiring nothing when n belongs to category (b).