Chapter 6
Mathematical Induction
One of the defining characteristics of the set of natural numbers N is th e s o-called
Principl e of Mathematical Induction.
The Principle of Mathematical Induction
If T is a subset of N such that
1. 1 2 T, and
2. For every k 2 N, if k 2 T, then .k C 1/ 2 T,
then T D N.
In many mathematics courses, this principle is given as an axiom for the s et
of natural numbers. Although we will not do so here, th e Principle of Mathemati-
cal Induction can be proved by using th e so-called Well-Orderin g Principle, which
states that every non -empty subset of the natural numbers contains a least element.
So in some courses, the Well-Ordering Principle is stated as an axiom of the natural
numbers. It should be noted, however, that it is also possible to assume the Princi-
ple of Mathematical Induction as an axiom and u se i t to prove the Well-Ordering
Principl e. We will only use the Principle of Mathematical Induction in this book.
30
Chapter 6. Mathematical Induction
31
6.1 Using the Principl e of Mathematical Induction
The primary use of the Principle of Mathematical Induction is to prove statements
of the form
.8n 2 N/ .P .n// ;
where P .n/ is some open sentence. Recall that a universally q uantified statement
like the preceding one is true if and only if the truth set T of the open sentence
P.n/ is the set N. So our goal is to prove that T D N, whi ch is the conclusion of
the Principle of Mathematical Indu ction. To verify the hypothesis of t he Principle
of Mathematical Inducti on, we must
1. Prove that 1 2 T. That is, prove t hat P .1/ is true.
2. Prove that if k 2 T, then .k C 1/ 2 T. That is, prove that if P .k/ is true,
then P .k C 1/ is true.
The first step is called the basis s tep or the initial step, and th e second step is
called the inductive step. This means that a proof by mathematical induction will
have the fo llowing form:
Procedure for a Proof by Mathematical Induction
To prove: .8n 2 N/ .P .n//
Basis step: Prove P .1/.
Inductive step: Prove that for each k 2 N,
if P.k/ is true, then P .k C 1/ is true.
We can then concl ude that P .n/ is true for all n 2 N.
Note that in the inductive step, we w ant to prove that the conditional statement “for
each k 2 N, if P.k/ then P .k C 1/” is tru e. So we wil l start the indu ctive step by
assuming that P.k/ is true. This assumption is called t he inductive assumption
or the inductive hypothesis.
The key to cons tructing a p roof of the inductive step is to discover how P.k C 1/
is related to P .k/ for an arbitrary natural number k. This is why it is important to
write down explicitly what P .k/ and P.k C 1/ are within the proof. No tice how
this is done in t he proof of the fo llowing proposition.
32
Chapter 6. Mathematical Induction
Proposition 6.1. For each natural number n,
1
2
C 2
2
C C n
2
D
n.n C 1/.2n C 1/
6
:
Proof. We wil l use a proof by mathematical induct ion. For each natural number
n, we let P .n/ be
1
2
C 2
2
C C n
2
D
n.n C 1/.2n C 1/
6
:
We first prove that P .1/ is true. Notice that
1 .1 C 1/ . 2 1 C 1/
6
D 1. This shows
that
1
2
D
1 .1 C 1/ .2 1 C 1/
6
;
which proves that P .1/ is true.
For the inductive step, we prove that for each k 2 N, if P .k/ is true, then P.k C1/
is true. So let k be a natural number and assume that P.k/ is true. That is, assume
that
1
2
C 2
2
C C k
2
D
k.k C 1/.2k C 1/
6
: (1)
The goal now is to prove that P .k C 1/ is true. That is , it must be proved that
1
2
C 2
2
C C k
2
C .k C 1/
2
D
.k C 1/ Œ.k C 1/ C 1 Œ2.k C 1/ C 1
6
D
.k C 1/ .k C 2/ .2k C 3/
6
: (2)
To do thi s, w e add .k C 1/
2
to both sides of equation (1) and algebraically rewrite
the right side of the resulting equation. This gives
1
2
C 2
2
C C k
2
C .k C 1/
2
D
k.k C 1/.2 k C 1/
6
C .k C 1/
2
D
k.k C 1/.2 k C 1/ C 6.k C 1/
2
6
D
.k C 1/ Œk.2k C 1/ C 6.k C 1/
6
D
.k C 1/
2k
2
C 7k C 6
6
D
.k C 1/ . k C 2/. 2k C 3/
6
:
Chapter 6. Mathematical Induction
33
Comparing this result to equation (2), we see that if P .k/ i s true, then P .k C 1/ is
true. Hence, the induct ive step has been establis hed, and b y th e Principle of Mathe-
matical Induction, we have proved that for each natural number n,
1
2
C 2
2
C C n
2
D
n.n C 1/.2n C 1/
6
.
6.2 The Extended Princi ple of Mathematical Induction
A little exploration shows that the following proposition appears to be true.
Proposition 6.2. For each integer n with n 4, nŠ > n
4
.
We would like to use mathematical induction to prove this, but the propositi on
has the added assumption that n 4. So to do this , we use a slight modifica-
tion of the Principle of Mathematical Induction called the Extended Principle of
Mathematical Induction.
The Extended Principle of Mathematical Induction
Let M be an i nteger. If T is a subset of Z such that
1. M 2 T, an d
2. For every k 2 Z with k M, if k 2 T, then .k C 1/ 2 T,
then T contains all integers greater than or equal t o M. That is,
fn 2 Z j n M g T.
The primary use of the Principle of Mathematical Induction is to prove statements
of the form
.8n 2 Z; with n M / .P .n//;
where M is an integer and P .n/ is some open sentence. (In most in duction proofs,
we will use a value of M that is greater than or equal to zero.) So our g oal is to
prove that the trut h set T of the predicate P .n/ contains all integers greater than or
equal to M. So to verify the hypothes is of the Exten ded Principle of Mathematical
Induction, we must
1. Prove that M 2 T. T hat is, prove that P .M / is true.
2. Prove that for every k 2 Z with k M, if k 2 T, then .k C 1/ 2 T. That is,
prove that if P .k/ is true, then P .k C 1/ is true.
34
Chapter 6. Mathematical Induction
As before, the first step is called the basis step or the initial step, and the sec-
ond step is called the inductive step. This means that a proof using the Extended
Principl e of Mathematical Induction will have the following form:
Using the Extended Principle of Mathematical Induction
Let M be an integer. To prove: .8n 2 Z with n M / .P.n//
Basis step: Prove P .M /.
Inductive step: Prove that fo r every k 2 Z with k M,
if P.k/ is true, then P .k C 1/ is true.
We can then concl ude that P .n/ is true for all n 2 Z with n M.
This is basically the same procedure as the one for using the Principle of Mathe-
matical Induction. The only difference is that the basis step uses an in teger M ot her
than 1. For this reason, when we w rite a proof that uses the Extended Principle of
Mathematical Induction, we often simply say we are going to use a proof by math-
ematical induct ion. We will prove Proposition 6.2 using the Extended Principle of
Mathematical Induction.
Proposition 6.2. For each integer n with n 4, nŠ > n
4
.
Proof. We will use a proof by math ematical induction. For this proof, we let
P.n/ be “nŠ > 2
n
.”
We first prove that P .4/ is true. Using n D 4, we see that 4Š D 24 and 2
4
D 16.
This means that 4Š > 2
4
and, hence, P .4/ is true.
For the inductive step, we prove that for all k 2 N with k 4, if P .k/ is true,
then P .k C 1/ is true. So let k be a natural number greater than or eq ual to 4, and
assume that P .k/ is true. That is, assu me that
kŠ > 2
k
: (1)
The goal is to prove that P .k C 1/ i s true o r that .k C 1/Š > 2
kC1
. Multiplying
both sid es of inequality (1) by k C 1 gives
.k C 1/ kŠ > .k C 1/ 2
k
; or
.k C 1/Š > .k C 1/ 2
k
: (2)
Chapter 6. Mathematical Induction
35
Now, k 4. Thus, k C 1 > 2 , and hence .k C 1/ 2
k
> 2 2
k
. This means that
.k C 1/ 2
k
> 2
kC1
: (3)
Inequali ties (2) and (3) show t hat
.k C 1/Š > 2
kC1
;
and this proves that if P .k/ is true, then P .k C 1/ is true. Thus, the inductive
step has been established, and so by mathematical induction, we have proved that
nŠ > 2
n
for each natural number n wi th n 4.
6.3 The Second Pr inciple of Mathematical Induction
Let P .n/ be
n is a p rime number or n is a produ ct of prime numbers.
Suppose we would like to use induction to prove that P.n/ is true for all natural
numbers greater than 1. We have seen that the idea of the inductive st ep in a proof
by i nduction i s to prove that if one statement in an infinite list of s tatements i s true,
then the next statement must also be true. The pro blem here is that when we factor
a composite number, we do not get to the previous case. For example, if assume
that P .39/ is true and we want to prove t hat P.40 / i s true, we could factor 40 as
40 D 2 20. So the assumption that P .39/ is true does not help us prove that P .40/
is true. What we would like to do is use P.2/ and P .20/.
This work is intended to show the need for ano ther principle of induction. In
the in ductive step of a pro of by inducti on, we assume one statement is true and
prove the next one is true. The idea o f this new principle is to assume t hat all of the
previous statements are true and use this assumption to prove the next statement is
true. This is stated formally in terms of subsets of natural numbers in the Second
Principle of Mathematical Induction .
36
Chapter 6. Mathematical Induction
The Second Principle of Mathematical Induction
Let M be an integer. If T is a subset of Z such that
1. M 2 T, an d
2. For every k 2 Z with k M, if fM; M C 1; : : : ; kg T, then
.k C 1/ 2 T,
then T contains all integers greater than or equal to M. That is,
fn 2 Z j n M g T.
The primary use of mathematical in duction is to prove statements of the form
.8n 2 Z; with n M / .P.n// ;
where M is an integer and P .n/ is some predicate. (For most proofs, M D 0
or M D 1. So our goal is to prove that the tru th set T of the predicate P.n/
contains all integers greater than or equal to M . To use th e Second Principl e of
Mathematical Induction, we must
1. Prove that M 2 T. That is, prove that P .M / is true.
2. Prove that for every k 2 N, if k M and fM; M C 1; : : : ; kg T, then
.k C 1/ 2 T. That is, prove t hat if P .M /; P .M C 1/; : : : ; P.k/ are true,
then P .k C 1/ is true.
As before, the first step is called the basis step or the initial step, and the
second step is called the i nductive step. This means that a proof using the Second
Principl e of Mathematical Induction will have the following form:
Using the Second Principle of Mathematical Induction
Let M be an i nteger. To prove: .8n 2 Z with n M / .P.n//
Basis step: Prove P.M /.
Inductive step: Let k 2 Z with k M . Prove that if
P.M /; P .M C 1/; : : : ; P .k/ are true, then
P.k C 1/ is true.
We can then concl ude that P .n/ is true for all n 2 Z with n M.
Chapter 6. Mathematical Induction
37
We will use this procedure to prove the proposition to prove the following p ropo-
sit ion.
Proposition 6.3. Each natural number greater t han 1 is either a pri me number or
is a p roduct of prime numbers.
Proof. We will us e the Second Principle of Mathematical Induction. We let P.n/
be
n is either a prime number or n is a product of prime numbers.
For the basis step, P .2/ is true since 2 is a prime number.
To prove the inductive step, we let k be a n atural number with k 2. We assume
that P .2/; P.3/; : : : ; P .k/ are true. That is, we assume that each of the natural
numbers 2; 3; : : : ; k is a pri me number or a product of prime numbers. The goal
is to prove that P.k C 1/ is true or that .k C 1/ is a prime number or a product of
prime numbers.
Case 1: If .k C 1/ is a prime number, then P.k C 1/ is true.
Case 2: If .k C 1/ is not a prime number, th en .k C 1/ can be factored into a
product of natural numbers with each one being less than . k C 1/. That is, there
exist natural numbers a and b with
k C 1 D a b; and 1 < a k and 1 < b k:
Using the in ductive assumption, this means that P .a/ and P .b/ are bo th true.
Consequently, a and b are prime numbers or are products of prime numbers. Si nce
k C 1 D a b, we conclude that .k C 1/ i s a prod uct of prime numbers. That is,
we conclude that P . k C 1/ is true. This proves the inductive step.
Hence, by the Second Principl e of Mathematical Induction, we conclude that
P.n/ is true for all n 2 N with n 2, and this means that each natural number
greater than 1 is either a prime number or is a product of prime numbers.
6.4 Pra ctice Problems for Chapter 6
1. (a) Calculate 1 C 3 C 5 C C .2n 1/ for several natural numbers n.
38
Chapter 6. Mathematical Induction
(b) Based on your work in part (a), if n 2 N, make a conjecture about the
value o f the sum 1 C 3 C 5 C C .2n 1/ D
n
P
j D1
.2j 1/.
(c) Use mathematical induction to prove your con jecture in p art (b).
2. Prove the foll owing:
Proposition. For each natural number n, 3 divides 4
n
1 .mod 3/.
3. For which natural numbers n is 3
n
greater than 5 C 2
n
? Stat e a propo sition
(with an appropriate quantifier) and prove it.
4. The Fi bonacci numbers are a sequence of natural numbers f
1
; f
2
; f
3
; : : : ; f
n
; : : :
defined recursively as fol lows:
f
1
D 1 and f
2
D 1, and
For each natural number n, f
nC2
D f
nC1
C f
n
.
In words, the recursion formula states that for any natural number n w ith
n 3, the n
th
Fibonacci number is the su m of the two previous Fib onacci
numbers. So we see that
f
3
D f
2
C f
1
D 1 C 1 D 2;
f
4
D f
3
C f
2
D 2 C 1 D 3; and
f
5
D f
4
C f
3
D 3 C 2 D 5:
(a) Calculate f
6
throu gh f
20
.
(b) Is every third Fibonacci number even? That is it true that for each
natural number n, f
3n
is even? Justi fy your conclusion.
(c) Is i t true that for each nat ural number n wi th n 2,
f
1
C f
3
C C f
2n1
D f
nC1
1? Justify yo ur conclusion.
5. Prove the foll owing prop osition using mathematical induction.
Proposition. For each n 2 N with n 8, there exist n onnegative
integers x an d y such that n D 3x C 5y.
Suggestion: Use the Second Principle of Induction and have the basi s step
be a proof that P .8/, P.9/, and P .10/ are true using an appropriate open
sentence for P .n/.
