= (k + 2)! − 1
= ((k + 1) + 1)! − 1.
k+1
X
Therefore
i · i! = ((k + 1) + 1)! − 1.
i=0
n
X
It follows by induction that
i · i! = (n + 1)! − 1 for every integer n ≥ 0. ■
i=0
159
The next example illustrates a trick that is occasionally useful. You
know that you can add equal quantities to both sides of an equation without
violating equality. But don’t forget that you can add unequal quantities to
both sides of an inequality, as long as the quantity added to the bigger
side is bigger than the quantity added to the smaller side. For example, if
x ≤ y and a ≤ b, then x + a ≤ y + b. Similarly, if x ≤ y and b is positive, then
x ≤ y + b. This oft-forgotten fact is used in the next proof.
Proposition
For each n ∈ N, it follows that 2n ≤ 2n+1 − 2n−1 − 1.
Proof. We will prove this with mathematical induction.
(1) If n = 1, this statement is 21 ≤ 21+1 − 21−1 − 1, which simplifies to
2 ≤ 4 − 1 − 1, which is obviously true.
(2) Suppose k ≥ 1.
We need to show that 2k ≤ 2k+1 − 2k−1 − 1 implies
2k+1 ≤ 2(k+1)+1−2(k+1)−1−1. We use direct proof. Suppose 2k ≤ 2k+1−2k−1−1,
and reason as follows:
2k
≤ 2k+1 − 2k−1 − 1
2(2k)
≤ 2(2k+1 − 2k−1 − 1)
(multiply both sides by 2)
2k+1
≤ 2k+2 − 2k − 2
2k+1
≤ 2k+2 − 2k − 2 + 1
(add 1 to the bigger side)
2k+1
≤ 2k+2 − 2k − 1
2k+1
≤ 2(k+1)+1 − 2(k+1)−1 − 1.
It follows by induction that 2n ≤ 2n+1 − 2n−1 − 1 for each n ∈ N.
■
We next prove that if n ∈ N, then the inequality (1 + x)n ≥ 1 + nx holds
for all x ∈ R with x > −1. Thus we will need to prove that the statement
Sn : (1 + x)n ≥ 1 + nx for every x ∈ R with x > −1
is true for every natural number n. This is (only) slightly different from
our other examples, which proved statements of the form ∀n ∈ N, P(n),
where P(n) is a statement about the number n. This time we are proving
something of form
∀n ∈ N, P(n, x),
where the statement P(n, x) involves not only n, but also a second variable x.
(For the record, the inequality (1 + x)n ≥ 1 + nx is known as Bernoulli’s
inequality.)
160
Mathematical Induction
Proposition
If n ∈ N, then (1 + x)n ≥ 1 + nx for all x ∈ R with x > −1.
Proof. We will prove this with mathematical induction.
(1) For the basis step, notice that when n = 1 the statement is (1 + x)1 ≥
1 + 1 · x , and this is true because both sides equal 1 + x.
(2) Assume that for some k ≥ 1, the statement (1 + x)k ≥ 1 + kx is true for
all x ∈ R with x > −1. From this we need to prove (1 + x)k+1 ≥ 1 + (k + 1)x.
Now, 1 + x is positive because x > −1, so we can multiply both sides of
(1 + x)k ≥ 1 + kx by (1 + x) without changing the direction of the ≥.
(1 + x)k(1 + x) ≥ (1 + kx)(1 + x)
(1 + x)k+1 ≥ 1 + x + kx + kx2
(1 + x)k+1 ≥ 1 + (k + 1)x + kx2
The above term kx2 is positive, so removing it from the right-hand side
will only make that side smaller. Thus we get (1 + x)k+1 ≥ 1 + (k + 1)x.
■
Next, an example where the basis step involves more than routine
checking. (It will be used later, so it is numbered for reference.)
Proposition 10.1
Suppose a1, a2, . . . , an are n integers, where n ≥ 2. If p
is prime and p | (a1 · a2 · a3 · · · an), then p | ai for at least one of the ai.
Proof. The proof is induction on n.
(1) The basis step involves n = 2. Let p be prime and suppose p | (a1a2).
We need to show that p | a1 or p | a2, or equivalently, if p - a1, then
p | a2. Thus suppose p - a1. Since p is prime, it follows that gcd(p, a1) = 1.
By Proposition 7.1 (on page 126), there are integers k and ` for which
1 = pk + a1 `. Multiplying this by a2 gives
a2 = pka2 + a1a2 `.
As we are assuming that p divides a1a2, it is clear that p divides the
expression pka2 + a1a2 ` on the right; hence p | a2. We’ve now proved that
if p | (a1a2), then p | a1 or p | a2. This completes the basis step.
(2) Suppose that k ≥ 2, and p | (a1 · a2 · · · ak) implies then p | ai for some ai.
¢
Now let p | (a1 · a2 · · · ak · ak+1). Then p | ¡(a1 · a2 · · · ak) · ak+1 . By what we
proved in the basis step, it follows that p | (a1 · a2 · · · ak) or p | ak+1. This
and the inductive hypothesis imply that p divides one of the ai.
■
Please test your understanding now by working a few exercises.
Proof by Strong Induction
161
10.1 Proof by Strong Induction
This section describes a useful variation on induction.
Occasionally it happens in induction proofs that it is difficult to show
that Sk forces Sk+1 to be true. Instead you may find that you need to use
the fact that some “lower” statements Sm (with m < k) force Sk+1 to be true.
For these situations you can use a slight variant of induction called strong
induction. Strong induction works just like regular induction, except that
in Step (2) instead of assuming Sk is true and showing this forces Sk+1
to be true, we assume that all the statements S1, S2, . . . , Sk are true and
show this forces Sk+1 to be true. The idea is that if it always happens that
the first k dominoes falling makes the (k + 1)th domino fall, then all the
dominoes must fall. Here is the outline.
Outline for Proof by Strong Induction
Proposition
The statements S1, S2, S3, S4, . . . are all true.
Proof. (Strong induction)
(1) Prove the first statement S1. (Or the first several Sn.)
(2) Given any integer k ≥ 1, prove (S1 ∧ S2 ∧ S3 ∧ · · · ∧ Sk) ⇒ Sk+1.
■
Strong induction can be useful in situations where assuming Sk is true
does not neatly lend itself to forcing Sk+1 to be true. You might be better
served by showing some other statement (Sk−1 or Sk−2 for instance) forces
Sk to be true. Strong induction says you are allowed to use any (or all) of
the statements S1, S2, . . . , Sk to prove Sk+1.
As our first example of strong induction, we are going to prove that
12 | (n4 − n2) for any n ∈ N. But first, let’s look at how regular induction
would be problematic. In regular induction we would start by showing
12 | (n4 − n2) is true for n = 1. This part is easy because it reduces to 12 | 0,
which is clearly true. Next we would assume that 12 | (k4 − k2) and try to
show this implies 12 | ((k+1)4 −(k+1)2). Now, 12 | (k4 −k2) means k4 −k2 = 12a
for some a ∈ Z. Next we use this to try to show (k + 1)4 − (k + 1)2 = 12b for
some integer b. Working out (k + 1)4 − (k + 1)2, we get
(k + 1)4 − (k + 1)2 = (k4 + 4k3 + 6k2 + 4k + 1) − (k2 + 2k + 1)
= (k4 − k2) + 4k3 + 6k2 + 6k
&nbs
p; = 12a + 4k3 + 6k2 + 6k.
At this point we’re stuck because we can’t factor out a 12. Now let’s see
how strong induction can get us out of this bind.
162
Mathematical Induction
Strong induction involves assuming each of statements S1, S2, . . . , Sk is
true, and showing that this forces Sk+1 to be true. In particular, if S1
through Sk are true, then certainly Sk−5 is true, provided that 1 ≤ k − 5 < k.
The idea is then to show Sk−5 ⇒ Sk+1 instead of Sk ⇒ Sk+1. For this to
make sense, our basis step must involve checking that S1, S2, S3, S4, S5, S6
are all true. Once this is established, Sk−5 ⇒ Sk+1 will imply that the other
Sk are all true. For example, if k = 6, then Sk−5 ⇒ Sk+1 is S1 ⇒ S7, so S7 is
true; for k = 7, then Sk−5 ⇒ Sk+1 is S2 ⇒ S8, so S8 is true, etc.
Proposition
If n ∈ N, then 12 | (n4 − n2).
Proof. We will prove this with strong induction.
(1) First note that the statement is true for the first six positive integers:
If n = 1, 12 divides n4 − n2 = 14 − 12 = 0.
If n = 2, 12 divides n4 − n2 = 24 − 22 = 12.
If n = 3, 12 divides n4 − n2 = 34 − 32 = 72.
If n = 4, 12 divides n4 − n2 = 44 − 42 = 240.
If n = 5, 12 divides n4 − n2 = 54 − 52 = 600.
If n = 6, 12 divides n4 − n2 = 64 − 62 = 1260.
(2) Let k ≥ 6 and assume 12 | (m4 − m2) for 1 ≤ m ≤ k. (That is, assume
statements S1, S2, . . . , Sk are all true.) We must show 12 | ¡(k+1)4 −(k+1)2¢.
(That is, we must show that Sk+1 is true.) Since Sk−5 is true, we have
12 | ((k − 5)4 − (k − 5)2). For simplicity, let’s set
m = k − 5, so we know
12 | (m4 −m2), meaning m4 − m2 = 12a for some integer a. Observe that:
(k + 1)4 − (k + 1)2 = (m + 6)4 − (m + 6)2
= m4 + 24m3 + 216m2 + 864m + 1296 − (m2 + 12m + 36)
= (m4 − m2) + 24m3 + 216m2 + 852m + 1260
= 12a + 24m3 + 216m2 + 852m + 1260
= 12¡a + 2m3 + 18m2 + 71m + 105¢.
As (a + 2m3 + 18m2 + 71m + 105) is an integer, we get 12 | ((k + 1)4 − (k + 1)2).
This shows by strong induction that 12 | (n4 − n2) for every n ∈ N.
■
Proof by Strong Induction
163
Our next example involves mathematical objects called graphs. In
mathematics, the word graph is used in two contexts. One context involves
the graphs of equations and functions from algebra and calculus. In
the other context, a graph is a configuration consisting of points (called
vertices) and edges which are lines connecting the vertices. Following
are some pictures of graphs. Let’s agree that all of our graphs will be in
“one piece,” that is, you can travel from any vertex of a graph to any other
vertex by traversing a route of edges from one vertex to the other.
v0
v1
v4
v2
v3
Figure 10.1. Examples of Graphs
A cycle in a graph is a sequence of distinct edges in the graph that
form a route that ends where it began. For example, the graph on the
far left of Figure 10.1 has a cycle that starts at vertex v1, then goes to v2,
then to v3, then v4 and finally back to its starting point v1. You can find
cycles in both of the graphs on the left, but the two graphs on the right do
not have cycles. There is a special name for a graph that has no cycles;
it is called a tree. Thus the two graphs on the right of Figure 10.1 are
trees, but the two graphs on the left are not trees.
Figure 10.2. A tree
Note that the trees in Figure 10.1 both have one fewer edge than vertex.
The tree on the far right has 5 vertices and 4 edges. The one next to it
has 6 vertices and 5 edges. Draw any tree; you will find that if it has n
vertices, then it has n − 1 edges. We now prove that this is always true.
164
Mathematical Induction
Proposition
If a tree has n vertices, then it has n − 1 edges.
Proof. Notice that this theorem asserts that for any n ∈ N, the following
statement is true: Sn : A tree with n vertices has n −1 edges. We use strong
induction to prove this.
(1) Observe that if a tree has n = 1 vertex then it has no edges. Thus it
has n − 1 = 0 edges, so the theorem is true when n = 1.
(2) Now take an integer k ≥ 1. We must show (S1 ∧ S2 ∧ · · · ∧ Sk) ⇒ Sk+1.
In words, we must show that if it is true that any tree with m vertices
has m − 1 edges, where 1 ≤ m ≤ k, then any tree with k + 1 vertices has
(k + 1) − 1 = k edges. We will use direct proof.
Suppose that for each integer m with 1 ≤ m ≤ k, any tree with m vertices
has m − 1 edges. Now let T be a tree with k + 1 vertices. Single out an
edge of T and label it e, as illustrated below.
T
· · ·
e
· · ·
· · ·
· · ·
· · ·
T1
T2
· · ·
· · ·
· · ·
Now remove the edge e from T, but leave the two endpoints of e. This
leaves two smaller trees that we call T1 and T2. Let’s say T1 has x
vertices and T2 has y vertices. As each of these two smaller trees has
fewer than k + 1 vertices, our inductive hypothesis guarantees that T1
has x − 1 edges, and T2 has y − 1 edges. Think about our original tree T.
It has x + y vertices. It has x − 1 edges that belong to T1 and y − 1 edges
that belong to T2, plus it has the additional edge e that belongs to
neither T1 nor T2. Thus, all together, the number of edges that T has is
(x − 1) + (y − 1) + 1 = (x + y) − 1. In other words, T has one fewer edges than
it has vertices. Thus it has (k + 1) − 1 = k edges.
It follows by strong induction that a tree with n vertices has n−1 edges.
■
Notice that it was absolutely essential that we used strong induction
in the above proof because the two trees T1 and T2 will not both have k
vertices. At least one will have fewer than k vertices. Thus the statement
Sk is not enough to imply Sk+1. We need to use the assumption that Sm
will be true whenever m ≤ k, and strong induction allows us to do this.
Proof by Smallest Counterexample
165
10.2 Proof by Smallest Counterexample
This section introduces yet another proof technique, called proof by small-
est counterexample. It is a hybrid of induction and proof by contradiction.
It has the nice feature that it leads you straight to a contradiction. It
is therefore more “automatic” than the proof by contradiction that was
introduced in Chapter 6. Here is the outline:
Outline for Proof by Smallest Counterexample
Proposition
The statements S1, S2, S3, S4, . . . are all true.
Proof. (Smallest counterexample)
(1) Check that the first statement S1 is true.
(2) For the sake of contradiction, suppose not every Sn is true.
(3) Let k > 1 be the smallest integer for which Sk is false.
(4) Then Sk−1 is true and Sk is false. Use this to get a contradiction.
■
Notice that this setup
leads you to a point where Sk−1 is true and
Sk is false. It is here, where true and false collide, that you will find a
contradiction. Let’s do an example.
Proposition
If n ∈ N, then 4 | (5n − 1).
Proof. We use proof by smallest counterexample. (We will number the
steps to match the outline, but that is not usually done in practice.)
(1) If n = 1, then the statement is 4 | (51 − 1), or 4 | 4, which is true.
(2) For sake of contradiction, suppose it’s not true that 4 | (5n − 1) for all n.
(3) Let k > 1 be the smallest integer for which 4 - (5k − 1).
(4) Then 4 | (5k−1 −1), so there is an integer a for which 5k−1 −1 = 4a. Then:
5k−1 − 1 = 4a
5(5k−1 − 1) = 5 · 4a
5k − 5 = 20a
5k − 1 = 20a + 4
5k − 1 = 4(5a + 1)
This means 4 | (5k −1), a contradiction, because 4 - (5k −1) in Step 3. Thus,
we were wrong in Step 2 to assume that it is untrue that 4 | (5n − 1) for
every n. Therefore 4 | (5n − 1) is true for every n.
■
166
Mathematical Induction
We next prove the fundamental theorem of arithmetic, which says
any integer greater than 1 has a unique prime factorization. For example,
12 factors into primes as 12 = 2 · 2 · 3, and moreover any factorization of 12
into primes uses exactly the primes 2, 2 and 3. Our proof combines the
techniques of induction, cases, minimum counterexample and the idea of
uniqueness of existence outlined at the end of Section 7.3. We dignify this
fundamental result with the label of “Theorem.”
Theorem 10.1
(Fundamental Theorem of Arithmetic) Any integer n > 1
has a unique prime factorization. That is, if n = p1 · p2 · p3 · · · pk and n =
a1 · a2 · a3 ··· a ` are two prime factorizations of n, then k = `, and the primes
pi and ai are the same, except that they may be in a different order.
Proof. Suppose n > 1. We first use strong induction to show that n has a
prime factorization. For the basis step, if n = 2, it is prime, so it is already
its own prime factorization. Let n ≥ 2 and assume every integer between 2
and n (inclusive) has a prime factorization. Consider n + 1. If it is prime,
then it is its own prime factorization. If it is not prime, then it factors as
n + 1 = ab with a, b > 1. Because a and b are both less than n + 1 they have
prime factorizations a = p1 · p2 · p3 · · · pk and b = p01 · p02 · p03 · · · p0 `. Then
n + 1 = ab = (p1 · p2 · p3 ··· pk)(p01 · p02 · p03 ··· p0 `)
Book of Proof Page 23
