Let’s spend a moment and get clear on what induction is and how it works in concrete terms. One often wishes to prove a certain statement true, where that statement says something about infinitely many things. For example:

Any even number squared is divisible by four.

One can check whether this holds for the first few even numbers: 2² = 4, yes; 4² = 16, yes; 6² = 36, yes. But eventually your arm is going to get tired of writing and you’ll probably be nowhere close to checking whether or not 272² is divisible by 4, let alone 3862456². Fortunately there is a easy way of rolling all this work into one:

Suppose x is an even number. Then, since being ‘even’ is the same as being twice some number, we know that x = 2y, where y is some natural number. We are interested in x² = (2y)² = 4y² . The important equality here is x² = 4y² , which says that the square of x is exactly 4 times some other number (namely y² , but that’s not important). Since being divisible by 4 is the same as being 4 times some number, we have therefore proved that x² is divisible by 4.

The crucial point about this proof is that is works simultaneously to prove the result for every even number. We were able to do this by taking advantage of the fact that the method of proof doesn’t depend at all on which even number you start with! So we abstracted away from the specifics by letting x stand for some (unnamed) even number and then proving the result for x, which must then hold true for every even number.

The preceding example was rather trivial, so it should at least convince you that sometimes getting infinitely many results out of a finite amount of work is not the lofty enterprise that it sounds. Mathematical induction works on the same principle of collapsing repetitive computations into a single, abstract com- putation which can then be applied again and again. But the implementation of induction is a bit different from the example we just saw.

Suppose that we wish to prove some result, call it R, about all the natural numbers, from 1 and up. And suppose also that we cannot find a way to do this directly; in other words, letting x stand for some natural number and then trying to prove R for x hits a dead end. We might find ourselves in the following situation:

“I can show that R is true for 1, easy enough, but that’s only one step among infinitely many. But wait, I can show R is true for 2 now also, by making use of the fact that R is true for 1. And now I can show that R is true for 3, using the fact that it’s true for 1 and 2.”

This looks promising, but there are still an infinite number of ‘steps’ to take: from 1 to 2, then to 3, then to 4, and so on. The induction insight is in realizing that if the reasoning behind each of these ‘steps’ is the same, no matter which step it is, then instead of abstracting away from the numbers, we can abstract from the steps. More formally, an inductive proof has two stages:

1. The Base Case. Prove the desired result for the number 1.
2. The Inductive Step. Prove that if the result is true for the numbers 1 through n, then it is also true for the number n + 1.

The inductive step is proved by first assuming that the result is true for the numbers 1 through n, and then using this assumption to show that it is also true for n + 1. This reasoning can seem circular at first—after all, the whole point is to try to prove that the result is true, so how can we be allowed to assume this? The answer we’ve already seen: the reasoning starts from the base case, where we prove directly that the result is true for 1. Then we can apply the inductive step in the case n = 1 to deduce that if the result is true for 1 (which we just verified) then it is also true for 2. Now we know the result is true for 1 and 2, and so we can reapply the inductive step in the case n = 2 to deduce that if the result is true for 1 and 2 (which it is), then it is also true for 3. And so on. In this manner the truth of the result for every number can be established by starting at 1 and working our way up. Far from being circular, mathematical induction is a canonical example of linear reasoning.

Sometimes it happens that we are able to complete the induction step without the full assumption that the result holds for al l the numbers 1 through to n. We will see several examples of this in the pages that follow, wherein we will only need to assume that the result is true for n in order to establish that it is also true for n + 1.