6.1: Comparing geometry and arithmetic

When students first meet “proof by induction”, it is often explained in a way that leaves them feeling distinctly uneasy, because it appears to break the fundamental taboo:

never assume what you are trying to prove.

This tends to leave the beginner in the position described by d'Alembert's quote at the start of the chapter: they may “press on” in the hope that “understanding will follow”, but a doubt often remains. So we encourage readers who have already met proof by induction to take a step back, and to try to understand afresh how it really works. This may require you to study the solutions (Section 6.10), and to be prepared to learn to write out proofs more carefully than, and rather differently from, what you are used to.

When we wish to prove a general result which involves a parameter n, where n can be any positive integer, we are really trying to prove infinitely many results all at once. If we tried to prove such a collection of results in turn, “one at a time”, not only would we never finish, we would scarcely get started (since completing the first million, or billion, cases leaves just as much undone as at the start). So our only hope is:

• to think of the sequence of assertions in a uniform way, as consisting of infinitely many different, but similar–looking, statements P(n), one for each n separately (with each statement depending on a particular n); and
• to recognise that the overall result to be proved is not just a single statement P(n), but the compound statement that “P(n) is true, for all $n\ge 1$ ”.

Once the result to be proved has been formulated in this way, we can

• use bare hands to check that the very first statement is true (usually P(1)); and
• try to find some way of demonstrating that,

– as soon as we know that “P(k) is true, for some (particular, but unspecified) $k\ge 1$”,

– we can prove in a uniform way that the next result $\mathbf{P}(k+1)$ is then automatically true.

Having implemented the first of the two induction steps, we know that P(1) is true.

The second bullet point above then comes into play and assures us that (since we know that P(1) is true), P(2) must be true.

And once we know that P(2) is true, the second bullet point assures us that P(3) is also true.

And once we know that P(3) is true, the second bullet point assures us that P(4) is also true.

And so on for ever.

We can then conclude that the whole sequence of infinitely many statements are all true – namely that:

“every statement P(n) is true”,

or that

“P(n) is true, for all $n\ge 1$.”

In other words, if we define S to be the set of positive integers n for which the statement P(n) is true, then S contains the element “1”, and whenever k is in S, so is $k+1$; hence, by the Principle of Mathematical Induction we know that S contains all positive integers.

At this stage we should acknowledge an important didactical (rather than mathematical) ploy in our recommended layout here. It is important to underline the distinction between

(i) the individual statements P(n) which are the separate ingredients in the overall statement to be proved, namely:

“P(n) is true, for all $n\ge 1$”,

where infinitely many individual statements have been compressed into a single compound statement, and

(ii) the induction step, where we

– assume some particular P(k) is known to be true, and

– show that the next statement $\mathbf{P}(k+1)$ is then automatically true.

To underline this distinction we consistently use a different “dummy variable” (namely “k”) in the latter case. This distinction is a psychological ploy rather than a logical necessity. However, we recommend that readers should imitate this distinction (at least initially).