The Principle of Mathematical Induction (PMI) may be the least intuitive proof method available to us. Indeed, at first, PMI may feel somewhat like grabbing yourself by the seat of your pants and lifting yourself into the air. Despite the indisputable fact that proofs by PMI often feel like magic, we need to convince you of the validity of this proof technique. It is one of the most important tools in your mathematical kit!

The simplest argument in favor of the validity of PMI is simply that it is axiomatic. This may seem somewhat unsatisfying, but the axioms for the natural number system, known as the Peano axioms, include one that justifies PMI. The Peano axioms will not be treated thoroughly in this book, but here they are:

1. There is a least element of \(\Naturals\) that we denote by \(0\).

2. Every natural number \(a\) has a successor denoted by \(s(a)\). (Intuitively, think of \(s(a) = a+1\).)

3. There is no natural number whose successor is \(0\). (In other words, -1 isn't in \(\Naturals\).)

4. Distinct natural numbers have distinct successors. (\(a \neq b \; \implies \; s(a) \neq s(b)\))

5. If a subset of the natural numbers contains \(0\) and also has the property that whenever \(a \in S\) it follows that \(s(a) \in S\), then the subset \(S\) is actually equal to \(\Naturals\).

The last axiom is the one that justifies PMI. Basically, if \(0\) is in a subset, and the subset has this property about successors¹Whenever a number is in it, the number's successor must be in it., then \(1\) must be in it. But if \(1\) is in it, then \(1\)'s successor (\(2\)) must be in it. And so on …

The subset ends up having every natural number in it.

On August 16th 2003, Ma Lihua of Beijing, China earned her place in the record books by single-handedly setting up an arrangement of dominoes standing on end (actually, the setup took 7 weeks and was almost ruined by some cockroaches in the Singapore Expo Hall) and toppling them. After the first domino was tipped over it took about six minutes before 303,621 out of the 303,628 dominoes had fallen. (One has to wonder what kept those other 7 dominoes upright …)

This is the model one should keep in mind when thinking about PMI: domino toppling. In setting up a line of dominoes, what do we need to do in order to ensure that they will all fall when the toppling begins? Every domino must be placed so that it will hit and topple its successor. This is exactly analogous to \((a \in S \, \implies s(a) \in S)\). (Think of \(S\) having the membership criterion, \(x \in S\) = “\(x\) will have fallen when the toppling is over.”) The other thing that has to happen (barring the action of cockroaches) is for someone to knock over the first domino. This is analogous to \(0 \in S\).

Rather than continuing to talk about subsets of the naturals, it will be convenient to recast our discussion in terms of infinite families of logical statements. If we have a sequence of statements, (one for each natural number) \(P_0\), \(P_1\), \(P_2\), \(P_3\), … we can prove them all to be true using PMI. We have to do two things. First — and this is usually the easy part — we must show that \(P_0\) is true (i.e. the first domino will get knocked over). Second, we must show, for every possible value of \(k\), \(P_k \implies P_{k+1}\) (i.e. each domino will knock down its successor). These two parts of an inductive proof are known, respectively, as the basis and the inductive step.

An outline for a proof using PMI:

Soon we'll do an actual example of an inductive proof, but first we have to say something REALLY IMPORTANT about such proofs. Pay attention! This is REALLY IMPORTANT! When doing the second part of an inductive proof (the inductive step), you are proving a UCS, and if you recall how that's done, you start by assuming the antecedent is true. But the particular UCS we'll be dealing with is \(\forall k, P_k \implies P_{k+1}\). That means that in the course of proving \(\forall n, P_n\) we have to assume that \(P_k\) is true. Now this sounds very much like the error known as “circular reasoning,” especially as many authors don't even use different letters (\(n\) versus \(k\) in our outline) to distinguish the two statements. (And, quite honestly, we only introduced the variable \(k\) to assuage a certain lingering guilt regarding circular reasoning.) The sentence \(\forall n, P_n\) is what we're trying to prove, but the sentence we need to prove in order to do that is \(\forall k, P_k \implies P_{k+1}\). This is subtly different — in proving that \(\forall k, P_k \implies P_{k+1}\) (which is a UCS!) we assume that \(P_k\) is true for some particular value of \(k\).

The sentence \(P_k\) is known as the inductive hypothesis. Think about it this way: If we were doing an entirely separate proof of \(\forall n, P_n \implies P_{n+1}\), it would certainly be fair to use the inductive hypothesis, and once that proof was done, it would be okay to quote that result in an inductive proof of \(\forall n, P_n\). Thus we can compartmentalize our way out of the difficulty!

Okay, so on to an example. In Section 4.1 we discovered a formula relating the sizes of a set \(A\) and its power set \({\mathcal P}(A)\). If \(|A| = n\) then \(|{\mathcal P}(A)| = 2^n\). What we've got here is an infinite family of logical sentences, one for each value of \(n\) in the natural numbers, \begin{equation*} |A| = 0 \implies |{\mathcal P}(A)| = 2^0, \end{equation*} \begin{equation*} |A| = 1 \implies |{\mathcal P}(A)| = 2^1, \end{equation*} \begin{equation*} |A| = 2 \implies |{\mathcal P}(A)| = 2^2, \end{equation*} \begin{equation*} |A| = 3 \implies |{\mathcal P}(A)| = 2^3, \end{equation*} et cetera.

This is exactly the sort of situation in which we use induction.

Here are a few pieces of advice about proofs by induction:

• Statements that can be proved inductively don't always start out with \(P_0\). Sometimes \(P_1\) is the first statement in an infinite family. Sometimes its \(P_5\). Don't get hung up about something that could be handled by renumbering things.

• In your final write-up you only need to prove the initial case (whatever it may be) for the basis, but it is a good idea to try the first several cases while you are in the “draft” stage. This can provide insights into how to prove the inductive step, and it may also help you avoid a classic error in which the inductive approach fails essentially just because there is a gap between two of the earlier dominoes.²See exercise b, the classic fallacious proof that all horses are the same color.

• It is a good idea to write down somewhere just what it is that needs to be proved in the inductive step — just don't make it look like you're assuming what needs to be shown. For instance in the proof above it might have been nice to start the inductive step with a comment along the following lines, “What we need to show is that under the assumption that any set of size \(k\) has a power set of size \(2^k\), it follows that a set of size \(k+1\) will have a power set of size \(2^{k+1}\).”

We'll close this section with a short discussion about nothing.

When we first introduced the natural numbers (\(\Naturals\)) in Chapter 1 we decided to follow the convention that the smallest natural number is 1. You may have noticed that the Peano axioms mentioned in the beginning of this section treat \(0\) as the smallest natural number. Many people follow Dr. Peano's convention, but we're going to stick with our original interpretation: \begin{equation*} \Naturals \, = \, \{ 1, 2, 3, \ldots \} \end{equation*}

Despite our stubbornness, we are forced to admit that many inductive proofs are made easier by treating the “first” case as being in truth the one numbered \(0\). We'll use the symbol \(\Naturals\) to indicate the set \({\mathbb N} \cup \{ 0 \}\).