Mathematical Induction
Eric Shapiro
Preliminaries
The natural numbers are the positive integers 1, 2, 3, 4, . . .
Motivation
In mathematics, we come across patterns all the time. For instance,
heres a pattern you may have noticed before:
1 + 3 + 5 = 9 = 32
1 + 3 + 5 + 7 = 16 = 42
..
.
2n-1
...
1 + 3 = 4 = 22
...
1 = 1 = 12
3
2
1 + 3 + 5 + 7 + + (2n 1) = n .
It turns out that for any natural number n, if you add the first n odd
numbers, you always get n2 . (Remember that the nth odd number is
2n 1.) But how can we come up with a convincing argument that
this pattern always holds?
We cant just keep adding more odd numbers because there are infinitely many of them, so wed never be able to finish if we tried.
Remember that the goal is to show that this holds for all natural
numbers!
We could probably use Figure 1 as a convincing visual argument that
our pattern is always true. However, that would only be applicable to
this particular pattern. We are more interested in finding a method
that we can apply to many problems.
The Principle of Mathematical Induction
Mathematical induction is a technique which we can often use to
show that certain patterns, such as the one given above, hold for all
2
1
3
1
Figure 1: A graphical depiction of the
pattern. From this picture, it should be
evident that adding together the first
n odd numbers literally results in a
square with side length n.
mathematical induction
natural numbers. This technique can be summarized as follows:
Mathematical Induction
Suppose P is a true/false statement about a natural number. If
Base Case: P(1) is true
Inductive Step: If P(n) is true then so is P(n + 1), for n 1.
then we have shown that P is true for every natural number.
The principle of mathematical induction
is actually equivalent to the statement
that any nonempty set of natural
numbers contains a smallest number.
This second assertion is obviously
true, and at the end of these notes I
have included a proof of the induction
principle from this assertion, if you are
interested.
This description might seem daunting at first, so lets look break it
down piece by piece.
We start off with a statement which is either true or false depending
on what number we feed it. The following are examples of such
statements:
P(n) := n is a prime number.
Q(n) := n is on fire.
R(n) := 1 + 3 + 5 + + (2n 1) = n2 .
S(n) := the nth domino will be knocked over.
We then must verify the base case, which means showing that if we
set n = 1, the resulting statement is true.
The last thing we have to do is show that if the statement holds for
an arbitrary number n, as long as n 1, then the statement also
holds for n + 1. This is the inductive step, which is usually where the
most work and insight are needed.
If we can do these two things, then we have shown that the statement
is true for every natural number! Just remember: base case, then
inductive step. Now lets look more closely at the example statements
from above:
By definition, P(n) is true only when n is prime. For instance, P(1) is
false because 1 is not prime, but P(2) is true because 2 is prime.
On the other hand, Q(n) is false no matter which n we plug into it
because natural numbers cannot, as far as I am aware, be on fire.
R(n) is the same statement we discussed earlier: that the sum of the
first n odd numbers is n2 . We will come back to this in a few moments and show it to be true for any n using an inductive argument.
The symbol := means is defined by.
mathematical induction
So, in other words, if we know for certain that the first domino will
fall, this means that every domino will fall because we have verified
both the base case and the inductive step. The argument we have just
given shows an infinite number of things to be true, which is fairly
impressive and is part of the power of inductive arguments.
Example 1
We now return to the first example we looked at, which is the assertion that
1 + 3 + 5 + + (2n 1) = n2 .
Equivalently, we can say that the sum of the first n odd numbers is
equal to n2 . Lets show this to be true using an induction argument!
Base Case: We need to show that the statement is true when we let
n = 1. This is simple enough, because 1 is already the sum of the first
1 odd numbers, and it is equal to its square. That is, 1 = 12 , so we
have shown that our base case is true.
Inductive Step: Now we will assume that 1 + 3 + 5 + + (2n 1) =
n2 , and we aim to show that 1 + 3 + 5 + + (2n 1) + (2n + 1) =
(n + 1)2 . That is, if we add the n + 1th odd number, we end up with
the square of n + 1. This requires a little bit of algebra, but isnt really
too difficult:
1 + 3 + 5 + + (2n 1) + (2n + 1) = n2 + (2n + 1)
= ( n + 1)2 .
S(1)
...
S(2)
...
...
What are the base case and inductive step in this example? The base
case is S(1), which corresponds to whether or not the first domino
will be knocked over. The inductive step is the fact that, if the nth
domino falls, then the n + 1th domino will also fall. The inductive
step is clearly true because each domino knocks over the next one
when it falls. However, if the first domino is never knocked over,
none of the other ones will be either. This illustrates the importance
of the base case! If the base case does not hold, then a proof by induction is invalid even if the inductive step does hold.
...
S(8)
...
...
For now, lets focus on S(n) because it is a helpful and illustrative
example of why induction works. Suppose we are a line of dominoes
extending infinitely to the right, all standing up and close enough
together that if one falls over it will hit the next domino in line.
Figure 2: An infinite line of dominoes.
If the base case S(1) is false then S(n)
is false for every n - i.e., none of the
dominoes ever fall over. If S(1) is true
then eventually every domino will fall,
because S(n) causes S(n + 1). That is,
the nth domino knocks over the n + 1th
domino when it falls.
mathematical induction
In the first step above, we used our assumption that 1 + 3 + 5 + +
(2n 1) = n2 . In the second step, we had to factor our resulting
quadratic. And weve now shown that our inductive step holds.
It follows from the principle of mathematical induction that our
assertion is true! The sum of the first n odd numbers is always n2 .
Example 2
This next example is one of my personal favorites, and its very visual. The statement we would like to show is true is as follows: A
2n 2n checkerboard can be covered by L-shaped tiles, with the exception of one arbitrary square.
Lets break this down a little bit first. When we say a 2n 2n checkerboard, we are talking about a square board with sides of length 2n .
So
n = 1 corresponds to the 2 2 board,
n = 2 corresponds to the 4 4 board,
n = 3 corresponds to the 8 8 board...
Now, by L-shaped tiles, we mean a tile comprised of three squares
which is shaped sort of like the letter L:
Figure 3: The 23 23 checkerboard,
which corresponds to the case n = 3.
Lastly, when we say a board can be covered by these tiles with the
exception of one arbitrary square, we mean something like this:
Its important to note that we could have left out any one square on
the board above and still been able to tile the rest of the board. It
does not matter which square we choose to exclude; we should still
mathematical induction
be able to cover the rest of the board. Try playing around with different sized boards, leaving one random square empty, and trying to
come up with such a tiling. For larger boards, this quickly becomes
no easy task.
It is our goal to show that we can cover any 2n 2n board in this
manner, and we will do so via induction.
Base Case: For our base case, we must show that the 2 2 board can
be tiled by L-shaped tiles, no matter which square we choose to omit.
Since there are only four squares on this board, we can brute-force
the base case by demonstrating that with any square missing, the rest
of the board can be tiled quite trivially:
We have shown that any 2 2 board can be covered in the desired
manner, so the base case has been verified.
Inductive Step: Next, we start off with the assumption that for an
arbitrary n 1, we can cover the 2n 2n checkerboard (with any one
arbitrary square omitted) as desired. We must use this information to
show that we can then tile the 2n+1 2n+1 board in the same fashion.
If we are given a 2n+1 2n+1 board, the missing tile necessarily lies
in exactly one of its four quadrants:
But each of these quadrants is actually a 2n 2n board, which we
know can be covered! So one of our quadrants has a missing tile already chosen for us, and honestly it doesnt really matter where that
mathematical induction
missing tile is because the rest of our argument will work regardless!
The other three quadrants we can cover however we choose, and we
do so in the following crafty way:
Weve now covered the entire 2n+1 2n+1 board with the exception of
our arbitrary missing square and a nice L-shaped hole in the middle,
which we can fill in with a single L-shaped tile, leaving only one
square missing. We have thus shown that the inductive step holds,
and so we have shown our assertion to be true!
(Optional) Proof of the Induction Principle
I stated in earlier that the principle of induction can be proved from
the fact that every nonempty set of natural numbers contains a smallest number. This fact is sometimes called the well-ordering principle.
Theorem. The principle of mathematical induction follows from the
well-ordering principle.
Proof. We give a proof by contradiction. That is, were going to assume that the statement is false and show that this leads logically to
an absurd result. We will then have shown that it cannot be false!
Suppose we are given a statement P and that the base case and inductive step hold, but that P is false for at least one natural number.
Let S represent the set of natural numbers n such that P(n) is false.
The set S is, by assumption, not empty. So we know from the wellordering principle that S contains a smallest number, which we will
call x. Certainly x 1 is not in the set S because x is the smallest
number in S. That is, P( x ) is false, but P( x 1) is true. However, our
inductive step tells us that P ( x 1) + 1 = P( x ) must be true - a
contradiction (a statement cannot be simultaneously true and false).
It follows that P(n) is true for every natural number n, completing
the proof.
