# Section5.1The principle of mathematical induction¶ permalink

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 1 , 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.

##### Exercise5.1.1

Verify that the following symbolic formulation has the same content as the version of the 5th Peano axiom given above. \begin{equation*} \forall S \subseteq \Naturals \; ( 0 \in S ) \land (\forall a \in \Naturals, a \in S \, \implies s(a) \in S) \implies \; S=\Naturals \end{equation*}

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:

 \begin{minipage}{.75\textwidth} Theorem $\displaystyle \forall n \in \Naturals, \; P_n$ Proof: (By induction) Basis: $\vdots$ \begin{minipage}[c]{1.7 in} (Here we must show that $P_0$ is true.) Inductive step: $\vdots$ \begin{minipage}[c]{1.7 in} (Here we must show that $\forall k, P_k \implies P_{k+1}$ is true.) Q.E.D.

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.

• 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. 2

• 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 \}$.

# Subsection5.1.1Exercises

1. Consider the sequence of numbers that are 1 greater than a multiple of 4. (Such numbers are of the form $4j+1$.) \begin{equation*} 1, 5, 9, 13, 17, 21, 25, 29, \ldots \end{equation*} The sum of the first several numbers in this sequence can be expressed as a polynomial. \begin{equation*} \sum_{j=0}^n 4j+1 = 2n^2 + 3n + 1 \end{equation*} Complete the following table in order to provide evidence that the formula above is correct.

 $n$ $\sum_{j=0}^n 4j+1$ $2n^2 + 3n + 1$ 0 $1$ $1$ 1 $1 + 5 = 6$ $2 \cdot 1^2 + 3 \cdot 1 + 1 = 6$ 2 $1 + 5 + 9 =$ \inlinehint{$15$} \inlinehint{$2 \cdot 2^2 + 3 \cdot 2 + 1 = 15$} 3 \inlinehint{$1 + 5 + 9 + 13 = 28$} \inlinehint{$2 \cdot 3^2 + 3 \cdot 3 + 1 = 28$} 4
\hint{I'm leaving the very last one for you to do.}

2. What is wrong with the following inductive proof of “all horses are the same color.”? Theorem Let $H$ be a set of $n$ horses, all horses in $H$ are the same color.

\hint{Look carefully at the stage from $n=2$ to $n=3$.}

3. For each of the following theorems, write the statement that must be proved for the basis — then prove it, if you can!

1. The sum of the first $n$ positive integers is $(n^2+n)/2$. \hint{The sum of the first $0$ positive integers is $(0^2 + 0)/2$. Or, if you prefer to start with something rather than nothing: The sum of the first $1$ positive integers is $(1^2+1)/2$. }

2. The sum of the first $n$ (positive) odd numbers is $n^2$. \hint{The sum of the first $0$ positive odd numbers is $0^2$. Or, the sum of the first $1$ positive odd numbers is $1^2$.}

3. If $n$ coins are flipped, the probability that all of them are “heads” is $1/2^n$. \hint{If $1$ coin is flipped, the the probability that it is “heads” is $1/2$. Or if we try it when $n=0$, If no coins are flipped the probability that all of them are heads is 1. Does that make sense to you? Is it reasonable that we would say it is 100% certain that all of the coins are heads in a set that doesn't contain any coins? }

4. Every $2^n \times 2^n$ chessboard — with one square removed — can be tiled perfectly 3  by L-shaped trominoes. (A trominoe is like a domino but made up of $3$ little squares. There are two kinds, straight \ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi and L-shaped \ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi . This problem is only concerned with the L-shaped trominoes.)

$n=1$$2 \times 2$—$n=0$
4. Suppose that the rules of the game for PMI were changed so that one did the following:

• Basis. Prove that $P(0)$ is true.

• Inductive step. Prove that for all $k$, $P_k$ implies $P_{k+2}$

$P_n$$n$$P(0)$$P(1)$$P(0)$$P(1)$$P(0)$$P(1)$
5. If we wanted to prove statements that were indexed by the integers, \begin{equation*} \forall z \in \Integers, \; P_z, \end{equation*} what changes should be made to PMI? \hint{A quick change would be to replace $\forall k, \; P_k \implies P_{k+1}$ in the inductive step with $\forall k, \; P_k \iff P_{k+1}$. While this would do the trick, a slight improvement is possible, if we treat the positive and negative cases for $k$ separately.}