New Zealand Mathematical Olympiad Committee

Induction
Chris Tuffley

1 “Proof by dominoes”

Mathematical induction is a useful tool for proving statements like “P is true for all natural numbers
n,” for example
n(n + 1)
1 + 2 + ··· + n = for all n ≥ 1. (1)
2
This statement is really a great long list of statements P (1), P (2), P (3), . . . that need to be proved,
one for each value of n, and we want a way to prove them all without having to resort to proving
the statement for n = 1, then for n = 2, then n = 3, then. . . because that way we’d never finish.
Sometimes (depending on the particular statement) there may be a way to prove them all at the same
time; but if such an argument doesn’t readily present itself, induction is a good trick to try. Of course,
like all tricks, there’s no guarantee it will work in a given situation, but like all tricks, it’s worth a try!
To understand how induction works, think about a long line of dominoes that you would like to topple
over.1 You can make them all fall over by

1. Checking that the dominoes are spaced closely enough that if one falls over, the next falls too;
then
2. Pushing over the first domino.

What happens next? The first domino pushes over the second, which pushes over the third, which
pushes over the fourth. . . and eventually all the dominoes fall over. The Principle of Mathematical
Induction works in much the same way: it says that if you want to prove a list of statements P (1),
P (2), P (3), . . . then it’s enough to show that

1. if P (n) is true, then so is P (n + 1), and

You can carry out these two steps in either order, and in fact they’re usually listed in the opposite
order, but I’ve written them this way because to my mind it fits the domino picture better. Step 1 is
called the inductive step; remember, because it’s an if . . . then statement, you prove it by assuming
that P (n) is true — this assumption is called the inductive hypothesis — and using this to show that
P (n + 1) is also true. Step 2 is called the base case.
Let’s see how this works in practice by proving equation (1) above.2 First let’s do the base case: this
means checking that the formula holds when n is replaced by 1. The left-hand side equals 1, and the
right-hand side is
1(1 + 1)
= 1.
2
1
No-one has yet succeeded in explaining induction without mentioning dominoes, so I won’t even try.
2
It’s practically compulsory to use this as one’s first example, so again I bow to tradition.

1
These two numbers are equal, which is good; we’ve established the base case. Next comes the inductive
step. We start by making the inductive hypothesis: we assume

n(n + 1)
1 + 2 + ··· + n =
2
is true for some fixed value of n. Using this assumption, let’s look at n + 1:

n(n + 1)
1 + 2 + · · · + n + (n + 1) = + (n + 1) (by the inductive hypothesis)
2
n2 + n 2n + 2
= +
2 2
n2 + 3n + 2
=
2
(n + 1)(n + 2)
= .
2
We’ve obtained the formula with n replaced with n + 1, which proves the inductive step. Since we’ve
now checked both steps 1 and 2, the Principle of Mathematical Induction tells us the formula is true
for all n, and we can happily use it without any further concerns.
A second example: Prove that n2 + n is even for all n. Checking the base case first, 12 + 1 = 2 is even
so we’re all set there. Suppose that s(n) = n2 + n is even for some fixed value of n and consider

s(n + 1) = (n + 1)2 + (n + 1)
= n2 + 2n + 1 + n + 1
= s(n) + 2n + 2.

By the inductive hypothesis s(n) is even, so s(n + 1) is a sum of even numbers, hence even also. This
proves the inductive step, so by the principle of mathematical induction n2 + n is even for all n. That
wasn’t too hard, but what about the following argument: since n2 + n = n(n + 1) and either n or
n + 1 is even, n2 + n must be even too. This is intended to illustrate what I meant above by “proving
them all at once”, and show that induction isn’t always the easiest way to go!

2 Variations

The basic outline of induction is as I’ve described above. The general idea is to try and establish a
link between the the statement for n = k and the statement for n = k + 1. There are times, however,
when this can’t be done, but with a little deviousness you can still get induction to work in some form.
I’ve outlined some possibilities below. This list is by no means exhaustive!

2.1 Base cases other than 1

It may happen that the result you want to prove is only true for n larger than some fixed number k,
such as 7. In this case you would proceed as above, using n = k as your base case, and (after carrying
out steps (1) and (2) above) conclude the result is true for all n ≥ k.

Example 1. Prove n! > 2n for all sufficiently large n.

2
Solution: First we have to figure out what “sufficiently large” is. Since 4! = 24 > 16 = 24 (and
3! = 6 < 8 = 23 ) let’s take n = 4 as our base case. We’ve already checked that so only the inductive
step is left; I’ll leave this up to you. Once it’s checked we’ll have the slightly more useful statement
that n! > 2n for all n ≥ 4.

2.2 Multiple base cases

Sometimes it may happen that finding a link between P (n) and P (n + 1) is difficult, but finding one
between P (n) and P (n + 2) is easy. In that case you can prove P (n) for all n by showing P (n) implies
P (n + 2) for your inductive step, and checking P (1) and P (2) as base cases. More generally, you can
establish P (n) implies P (n + k) as an inductive step and check P (1), . . . , P (k) as base cases.

Exercise 1. Suppose you have an unlimited supply of 5 and 8 cent stamps. Show you can use these
to make any amount of postage greater than 27 cents.

2.3 Strong induction

The principle of strong induction replaces the inductive hypothesis that P (n) is true with the stronger
assumption that P (j) is true for all j ≤ n. Specifically, you show that

1. if P (j) is true for all j ≤ n, then so is P (n + 1), and

2. P (1) is true.

Exercise 2. You and I are playing a game with raisins. We start with two non-empty piles of raisins
on the table, and take turns making moves. A move consists of eating all the raisins in one pile and
dividing the second into two non-empty (and not necessarily equal) piles. The game continues until
one of us can’t move; that player loses. Show that if one of the piles starts out with an even number
of raisins then the first player can win.

Strong induction enters the picture in this problem because we need to assume that we can win any
game with fewer raisins if it starts out with at least one pile having an even number of raisins.

2.4 “Top down” induction and the Well-Ordering Principle

Induction arguments are sometimes framed from the top down rather than from the bottom up. In this
setting one looks at a smallest counterexample (sometimes colourfully called a “minimal criminal”),
and uses it to derive a contradiction. One approach is to simply prove the inductive step, thereby
showing that the purported counterexample isn’t one after all; but a second is to show that the
counterexample can be modified to give a smaller one, thereby contradicting the minimality. This
second approach is particularly fruitful when one’s trying to prove something about fairly complicated
objects (say, graphs) by induction over their size (say, the number of edges plus vertices).
The “smallest counterexample” used above is given to us by the Well-Ordering Principle. This principle
is equivalent to the Principle of Mathematical Induction, and states that any non-empty subset S of
the natural numbers has a least element. To show that P (n) is true for all n, we let S be the set of
natural numbers for which P (n) is false. If (heaven forbid!) S is non-empty, then its least element k
is the smallest counterexample we were looking for.

3
Proofs using the Well-Ordering Principle aren’t always immediately recognisable as inductive proofs,
as the proof of the following theorem shows.

Theorem 1 (The division algorithm). Let a and b be integers with b > 0. Then there exist unique
integers q and r such that a = bq + r and 0 ≤ r < b.

The integers q and r are called the quotient and remainder respectively. I’ll prove the existence part
(since this is where the WOP is used), and just point you in the right direction for uniqueness.

Proof. Let S be the set {a − bk|k is an integer and a − bk ≥ 0}. This set is non-empty (check this!)
so by the Well-Ordering Principle it has a least element r = a − bq. Then a = bq + r and r ≥ 0, so we
just need to show that r < b.
If r ≥ b then a − b(q + 1) = r − b ≥ 0, so r0 = a − b(q + 1) belongs to S. But then r = r0 + b is greater
than r, contradicting the fact that r is the smallest element of S. So we must have r < b, as required.
To establish uniqueness, suppose that a = bq+r = bq 0 +r0 with 0 ≤ r, r0 < b. Re-arrange bq+r = bq 0 +r0
to show that b divides r − r0 , and use this to conclude that r − r0 = 0. You’ll need to use the condition
that 0 ≤ r, r0 < b to do this.

2.5 Multiple variables

Suppose you have a statement of the form “P is true for all n, m ≥ 1”, for example

m! (m + 1)! (m + n)! (m + n + 1)!

You could try proving it by first doing induction over one of the variables, then induction over the
second (how should your inductive hypotheses be framed for each variable?). Which one you choose
can sometimes (but not always) make your life easier or harder, and it’s worth thinking about which
way to do it before wading in.

Exercise 3. Prove the above identity two ways, by induction over n first, then by induction over m
first.

2.6 Mixing forwards and backwards induction

The arithmetic mean-geometric mean inequality says that if a1 , a2 , . . . , an are non-negative numbers
then
a1 + a2 + · · · + an
(a1 a2 . . . an )1/n ≤
n
(the left-hand side is the geometric mean of the ai and the right-hand side is the ordinary mean, also
known as the arithmetic mean). This can be proved by forwards induction over the powers of two (if
it’s true for one power of two, it’s true for the next), then backwards induction to fill in the gaps! By
backwards induction I mean showing P (n − 1) is true if P (n) is — in this case you’d use the powers
of two as your base cases. Try it for yourself!

4
3 A false proof

The following argument is due to George Pólya, and everyone should see it at some point. We’ll prove
by induction that all horses are the same colour. More precisely, we’ll show that any n horses are all
the same colour for each n ≥ 1 — that ought to do it.
The base case (n = 1) is obvious, so let’s assume that given a set of n horses, they’re all the same
colour. Take a set of n + 1 horses, and designate one of them the “test horse”. Remove one of the
other horses, leaving a herd of n; by the inductive hypothesis, they’re all the same colour, and in
particular, they’re all the same colour as the test horse. Put the horse you removed back, and remove
one of the others, again leaving a set of n horses; by the inductive assumption, they’re all the same
colour, and we see that the horse previously removed is the same colour as the test horse also. So all
n + 1 of them are same colour, which proves the inductive step. So all horses are the same colour.

Exercise 4. Find the flaw in this argument!

4 Problems

Have a go at the following problems. They vary in difficulty; the harder ones are probably towards
the end. In some cases you’ll have to figure out just what it is you want to prove using induction first;
in others, you may come up with a non-inductive proof too.

1. Prove 2n > n for all n ≥ 1.

2. Prove that

(a) 1 + 3 + 5 + · · · + (2n − 1) = n2 ,
n(n + 1)(2n + 1)
(b) 12 + 22 + 32 + · · · + n2 = ,
6
n2 (n + 1)2
(c) 13 + 23 + 33 + · · · + n3 = .
4
3. Show that 2n > n2 for sufficiently large n.

4. Show that a set of n elements has 2n subsets.

5. The Fibonacci numbers are defined by f0 = f1 = 1 and fn+1 = fn + fn−1 for n ≥ 2. Show that
the nth Fibonacci number is given by

(φ+ )n − (φ− )n
fn = ,
φ+ − φ−
√ √
1+ 5 1− 5
where φ+ = and φ− = are the roots of x2 = x + 1.
2 2
(See Recurrence Relations [1] to learn how you might come up with this formula in the first
place.)

6. Use strong induction to prove that every integer n ≥ 2 may be expressed as a product of prime
numbers.

5
 7. (The Tower of Hanoi) This game is played with three pegs and n discs, each a different size to
the rest and each with a hole in the centre so it can fit over the pegs. All the discs start out on
one of the pegs, stacked in increasing order of size; the object of the game is to move them all
to one of the other pegs. You’re only allowed to move one disc at a time, and you’re not allowed
to put any disc on top of one that’s smaller. How many moves are required?

8. Given a (2m + 1) × (2n + 1) chessboard in which all four corners are black squares, show that
if one removes any one white square and any two black squares, the remaining board can be
covered with dominoes (1 × 2 rectangles).

9. Prove the arithmetic-geometric mean inequality (see Section 2.6 above).

10. (Euler’s formula for graphs in the plane) Let G be a connected graph drawn in the plane with
v vertices and e edges that divide the plane into f regions or “faces” (we consider the “outside”
to be a face too). Then v − e + f = 2. Prove this by induction on the number of vertices plus
edges (you may wish to consider a “top-down” approach).
Extra: use this fact to determine the maximum number of “pieces” you can cut a pizza into
with n straight cuts.

11. Suppose n disks, black on one side and white on the other, are laid out in a straight line with
a random arrangement of black sides up. You are playing a game of solitaire, in which a turn
consists of removing a black disk and flipping over its immediate neighbors, if any. (Two disks
are not considered immediate neighbors if there used to be a disk between them that is now
gone.) A game is winnable if it is possible to remove all n disks. Describe all winnable games,
and devise a strategy which will win all winnable games.
Hint: Once you think you can describe all winnable games, prove your guess using induction.
Note that not only must you show you can win all games you think are winnable, but you must
also prove that all others aren’t winnable. Do this by induction too.

References

[1] Chris Tuffley. Recurrence Relations. NZ Mathematical Olympiad Committee, January 2009.
Available from www.mathsolympiad.org.nz.

3rd March 2009