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:
There is a least element of \(\Naturals\) that we denote by \(0\).
Every natural number \(a\) has a successor denoted by \(s(a)\).
(Intuitively, think of \(s(a) = a+1\).)
There is no natural number whose successor is \(0\). (In other
words, 1 isn't in \(\Naturals\).)
Distinct natural numbers have distinct successors.
(\(a \neq b \; \implies \; s(a) \neq s(b)\))
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, 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 singlehandedly 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.
Theorem5.1.2
For all finite sets \(A\), \(\displaystyle A = n \implies {\mathcal P}(A) = 2^n\).
Let \(n = A\) and proceed by induction on \(n\).
Basis: Suppose \(A\) is a finite set and \(A = 0\), it follows
that \(A = \emptyset\). The power set of \(\emptyset\) is \(\{ \emptyset \}\)
which is a set having 1 element. Note that \(2^0 = 1\).
Inductive step: Suppose that \(A\) is a finite set with \(A = k+1\). Choose some particular element of \(A\), say \(a\), and note that
we can divide the subsets of \(A\) (i.e. elements of \({\mathcal P}(A)\)) into
two categories, those that contain \(a\) and those that don't.
Let \(S_1 = \{ X \in {\mathcal P}(A) \suchthat a \in X \}\) and let
\(S_2 = \{ X \in {\mathcal P}(A) \suchthat a \notin X \}\). We have
created two sets that contain all the elements of \({\mathcal P}(A)\),
and which are disjoint from one another. In symbolic form,
\(S_1 \cup S_2 = {\mathcal P}(A)\) and \(S_1 \cap S_2 = \emptyset\).
It follows that \({\mathcal P}(A) = S_1 + S_2\).
Notice that \(S_2\) is actually the power set of the \(k\)element set
\(A \setminus \{ a \}\). By the inductive hypothesis, \(S_2 = 2^k\).
Also, notice that each set in \(S_1\) corresponds uniquely to a set in
\(S_2\) if we just remove the element \(a\) from it. This shows that
\(S_1 = S_2\). Putting this all together we get that
\({\mathcal P}(A) = 2^k + 2^k = 2(2^k) = 2^{k+1}\).
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 writeup 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.
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 \}\).
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.}
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.
We proceed by induction on \(n\).
Basis: Suppose \(H\) is a set containing 1 horse. Clearly
this horse is the same color as itself.
Inductive step: Given a set of \(k+1\) horses \(H\) we can
construct two sets of \(k\) horses. Suppose \(H = \{ h_1, h_2, h_3, \ldots h_{k+1} \}\). Define \(H_a = \{ h_1, h_2, h_3, \ldots h_{k} \}\) (i.e. \(H_a\) contains
just the first \(k\) horses) and \(H_b = \{ h_2, h_3, h_4, \ldots h_{k+1} \}\)
(i.e. \(H_b\) contains the last \(k\) horses). By the inductive hypothesis
both these sets contain horses that are “all the same color.” Also,
all the horses from \(h_2\) to \(h_k\) are in both sets so both \(H_a\) and
\(H_b\) contain only horses of this (same) color. Finally, we conclude that
all the horses in \(H\) are the same color.
\hint{Look carefully at the stage from \(n=2\) to \(n=3\).}

For each of the following theorems, write the statement that must be
proved for the basis — then prove it, if you can!
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\). }
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\).}
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? }
Every \(2^n \times 2^n\) chessboard — with one square removed — can
be tiled perfectly by Lshaped 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 Lshaped
\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 Lshaped trominoes.)
\(n=1\)\(2 \times 2\)—\(n=0\)

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)\)
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.}