Chapter 3

Mathematical induction

In the previous chapter, we described three methods of deductive proofs. Here, we describe proof by
induction. But first, what is the difference?
• deduction is reasoning from the general to the specific, and
• induction is reasoning from the specific to the general.
Often in mathematics we wish to make generalizations about things we have observed. In fact,
often we want to prove a general statement based on what we can prove about a particular instance of
that statement. An example of this is when we wish to prove that a statement is true for an infinite
number of cases. Since we can only prove any particular statement for a finite number of cases we
need some way to extend this idea. The following idea is a common tool used to accomplish this goal.
Axiom 3.1 (The Principle of Mathematical Induction). Let P (n) be a statement defined for
integers n, and let a be a fixed integer. Suppose the following two statements are true.
(i) P (a) is true. [the base case]
(ii) For all integers k ≥ a, if P (k) is true then P (k + 1) is true. [the inductive step]

Then the statement P (n) is true for all integers n ≥ a.

How can we use induction to prove a statement? There are two things to do. First we need to
prove the base case. That is, we need to prove that P (a) is true.
Note that when we write P (k) we mean a statement about the integer k and
not some polynomial P . For instance, if we wish to prove that for every n in the
set of natural numbers N, the sum 1 + 2 + · · · + n = n(n+1)
2 , then we can let P (k)
be the statement “the sum of the first k natural numbers is k(k+1) 2 .” However, we
would not write
k(k + 1)
P (k) = 1 + 2 + · · · + k =
2
since P (k) has a truth value (of either true or false) rather than a numerical value
like k(k+1)
2 .
Secondly, we would need to prove the implication in part (ii) of the axiom. That is, we prove the
implication P (k) ⇒ P (k + 1), using an appropriate method. A good first step in a proof by induction
is to identify what P (k) represents. To give your proof some structure, and so that you don’t fall into

1
2 CHAPTER 3. MATHEMATICAL INDUCTION

the trap of thinking of P (k) as some function, it is a good idea to explicitly write down what P stands
for.
n(n+1)
Example 3.2. If n is a natural number, then the sum of the first n natural numbers is 2 .
Since we are making an assertion about an arbitrary natural number, we really
mean that it is true for all natural numbers. Hence, this is a convenient place to
use induction. (Of course, you should look at a few examples to convince yourself
that this statement could be true before you start trying to prove it.)
3·4
1+2+3 = 6 and =6
2
6·7 42
1+2+3+4+5+6 = 21 and = = 21
2 2
10 · 11 110
1 + 2 + · · · + 9 + 10 = 55 and = = 55
2 2

Proof. [By induction.] Let P (n) be the statement “the sum of the first n natural numbers is n(n+1)
2 .”
(Now we need to show that P (1) is true.)1 Since 1 = 1·2 2
2 , we can see that P (1) is true. (This takes
care of the base case, now we need to prove the inductive step.)
Now assume that P (k) is true for some natural number k. That is,

k(k + 1)
1 + 2 + ··· + k = .
2
Then, to see that P (k + 1) is true, observe that

k(k + 1)
1 + 2 + · · · + k + (k + 1) = + (k + 1) (Why?)
2

k 2 + k 2k + 2
= + (Why?)
2 2

k 2 + 3k + 2
= (Why?)
2
(k + 1)(k + 2)
= (Why?)
2
(k + 1)((k + 1) + 1)
= .
2
Thus P (k + 1) is true. (This proves the induction step, “P (k) ⇒ P (k + 1)”.) Therefore, by the axiom
of induction, the sum of the first n natural numbers is given by n(n+1)
2 .

1 The parenthetical remarks are not so much a part of the proof, but rather what you should be thinking as you are

constructing a proof.
2 Notice here that we haven’t really added anything to anything else. We usually think of addition in terms of adding

two things (like numbers) to each other to make another number. In this case we are “adding” only a single term, which
makes the sum the same as the single number we have added. We often make conventions like this in mathematics, such
as defining 0! to be 1.
 3

Problem 3.3. If n is a natural number, then the sum of the first n even numbers is n2 + n.
Problem 3.4. If n is a natural number, then the sum of the first n odd numbers is n2 .
Problem 3.5. If n is a natural number, then the sum of the cubes of the first n natural numbers is
h i2
equal to n(n+1)
2 .

Problem 3.6. If n is a natural number, then n! ≥ 2n−1 .

Problem 3.7. For all n ∈ N, the expression n2 + n + 41 is a prime number.
Problem 3.8. If a and r are real numbers with r 6= 1 and n is a natural number, then

a(rn+1 − 1)
a + ar + ar2 + · · · + arn = .
r−1

Problem 3.9. If n is a natural number, then

(2n)!
2 · 6 · 10 · 14 · · · (4n − 2) = .
n!

Problem 3.10. If x ∈ R with x > −1 and n is a natural number, then

(1 + x)n ≥ 1 + nx.

Sometimes the base case does not correspond to the natural number 1. This may be the case
whenever some statement is not true for some number of cases. The following three problems illustrate
this.
Problem 3.11. If n is a natural number and n ≥ 4, then 3n > 2n2 + 3n. [Note that the inequality is
false if n < 4.]
Problem 3.12. If n is a natural number and n ≥ 4, then n! > n2 . [Note that the inequality is false
if n < 4.]
There is another formulation of induction where we assume a bit more information at the beginning.
This method is sometimes called complete induction or strong induction.
Axiom 3.13 (Strong Mathematical Induction). Let P (n) be a statement defined for integers n,
and let both a and b be fixed integers with a ≤ b. Suppose the following two statements are true.

(i) P (a), P (a + 1), . . . , and P (b) are all true. [the base case]

(ii) If m is an integer with m ≥ b, then the implication

“[P (j) for all a ≤ j ≤ m] ⇒ P (m + 1)” is true. [the inductive step]

Then the statement P (n) is true for all integers n ≥ a.

Note the differences between the original induction axiom and this one. The base case may contain
proofs for several initial values; and in the inductive step, we are not only assuming P (m) to show
P (m + 1), but rather that P (j) is true for all j from a to m.
Problem 3.14. Every natural number greater than 1 is either prime or the product of primes.
Problem 3.15. Let a1 = 1, a2 = 3, and for n > 2 let an = an−1 + an−2 . Show that an < (7/4)n for
all natural numbers.
4 CHAPTER 3. MATHEMATICAL INDUCTION

Problem 3.16. Let a1 = 1, a2 = 2, a3 = 3, and for each natural number greater than 3, define
an = an−1 + an−2 + an−3 . Prove that an < 2n for all n ∈ N.
Problem 3.17. How was the axiom of strong mathematical induction misapplied in the proof of the
following obviously false statement?

“Theorem.” All rabbits are the same color.

Proof. Let P (n) denote the following statement:
Any given n rabbits are the same color.
If we can show that P (n) is true for all n ∈ N, then we will clearly have proven that all
rabbits are the same color. We proceed by induction.
Clearly, if we have only one rabbit, then that rabbit will be the same color as
itself. Now assume that for all j ≤ k, any given j rabbits are the same color. We must
show that any given k + 1 rabbits are the same color. We start by picking an arbitrary
collection of k + 1 rabbits. Number the rabbits 1 to k + 1. If we consider the first and
(k + 1)th rabbits, then these two must be the same color by the induction hypothesis.
Since the first rabbit and the second through k th rabbits are all the same color by the
same reason, we must conclude that all k + 1 rabbits are the same color. Finally, the
axiom of strong induction tells us that “any given n rabbits are the same color”.