to disprove it we must prove its negation. Symbolically, the statement is
Disproving Existence Statements
151
∃ x ∈ R, x4 < x < x2, so its negation is
∼ (∃ x ∈ R, x4 < x < x2) = ∀ x ∈ R, ∼ (x4 < x < x2).
Thus, in words the negation is:
For every real number x , it is not the case that x4 < x < x2 .
This can be proved with contradiction, as follows. Suppose for the
sake of contradiction that there is an x for which x4 < x < x2. Then x must
be positive since it’s greater than the non-negative number x4. Dividing
all parts of x4 < x < x2 by the positive number x produces x3 < 1 < x. Now
subtract 1 from all parts of x3 < 1 < x to obtain x3 − 1 < 0 < x − 1 and reason
as follows:
x3 − 1 < 0 < x − 1
(x − 1)(x2 + x + 1) < 0 < (x − 1)
x2 + x + 1 < 0 < 1
(Division by x − 1 did not reverse the inequality < because the second line
above shows 0 < x − 1, that is, x − 1 is positive.) Now we have x2 + x + 1 < 0,
which is a contradiction because x being positive forces x2 + x + 1 > 0
We summarize our work as follows.
The statement “There is a real number x for which x4 < x < x2” is false
because we have proved its negation “For every real number x , it is not the
case that x4 < x < x2 .”
As you work the exercises, keep in mind that not every conjecture will be
false. If one is true, then a disproof is impossible and you must produce a
proof. Here is an example:
Example 9.4
Either prove or disprove the following conjecture.
Conjecture
There exist three integers x, y, z, all greater than 1 and no
two equal, for which xy = yz.
This conjecture is true. It is an existence statement, so to prove it we
just need to give an example of three integers x, y, z, all greater than 1 and
no two equal, so that xy = yz. A proof follows.
Proof. Note that if x = 2, y = 16 and z = 4, then xy = 216 = (24)4 = 164 = yz. ■
152
Disproof
9.3 Disproof by Contradiction
Contradiction can be a very useful way to disprove a statement. To see
how this works, suppose we wish to disprove a statement P. We know
that to disprove P, we must prove ∼ P. To prove ∼ P with contradiction,
we assume ∼∼ P is true and deduce a contradiction. But since ∼∼ P = P,
this boils down to assuming P is true and deducing a contradiction. Here
is an outline:
How to disprove P with contradiction:
Assume P is true, and deduce a contradiction.
To illustrate this, let’s revisit Example 9.3 but do the disproof with
contradiction. You will notice that the work duplicates much of what we
did in Example 9.3, but is it much more streamlined because here we do
not have to negate the conjecture.
Example 9.5
Disprove the following conjecture.
Conjecture: There is a real number x for which x4 < x < x2.
Disproof. Suppose for the sake of contradiction that this conjecture is true.
Let x be a real number for which x4 < x < x2. Then x is positive, since it is
greater than the non-negative number x4. Dividing all parts of x4 < x < x2
by the positive number x produces x3 < 1 < x. Now subtract 1 from all parts
of x3 < 1 < x to obtain x3 − 1 < 0 < x − 1 and reason as follows:
x3 − 1 < 0 < x − 1
(x − 1)(x2 + x + 1) < 0 < (x − 1)
x2 + x + 1 < 0 < 1
Now we have x2 + x + 1 < 0, which is a contradiction because x is positive.
Thus the conjecture must be false.
■
Exercises for Chapter 9
Each of the following statements is either true or false. If a statement is true,
prove it. If a statement is false, disprove it. These exercises are cumulative,
covering all topics addressed in Chapters 1–9.
1. If x, y ∈ R, then |x + y| = |x| + |y|.
2. For every natural number n, the integer 2n2 − 4n + 31 is prime.
Disproof by Contradiction
153
3. If n ∈ Z and n5 − n is even, then n is even.
4. For every natural number n, the integer n2 + 17n + 17 is prime.
5. If A, B, C and D are sets, then (A × B) ∪ (C × D) = (A ∪ C) × (B ∪ D).
6. If A, B, C and D are sets, then (A × B) ∩ (C × D) = (A ∩ C) × (B ∩ D).
7. If A, B and C are sets, and A × C = B × C, then A = B.
8. If A, B and C are sets, then A − (B ∪ C) = (A − B) ∪ (A − C).
9. If A and B are sets, then P(A) − P(B) ⊆ P(A − B).
10. If A and B are sets and A ∩ B = ;, then P(A) − P(B) ⊆ P(A − B).
11. If a, b ∈ N, then a + b < ab.
12. If a, b, c ∈ N and ab, bc and ac all have the same parity, then a, b and c all have
the same parity.
13. There exists a set X for which R ⊆ X and ; ∈ X .
14. If A and B are sets, then P(A) ∩ P(B) = P(A ∩ B).
15. Every odd integer is the sum of three odd integers.
16. If A and B are finite sets, then |A ∪ B| = |A| + |B|.
17. For all sets A and B, if A − B = ;, then B 6= ;.
18. If a, b, c ∈ N, then at least one of a − b, a + c and b − c is even.
19. For every r, s ∈ Q with r < s, there is an irrational number u for which r < u < s.
20. There exist prime numbers p and q for which p − q = 1000.
21. There exist prime numbers p and q for which p − q = 97.
22. If p and q are prime numbers for which p < q, then 2p + q2 is odd.
23. If x, y ∈ R and x3 < y3, then x < y.
24. The inequality 2x ≥ x + 1 is true for all positive real numbers x.
25. For all a, b, c ∈ Z, if a | bc, then a | b or a | c.
26. Suppose A, B and C are sets. If A = B − C, then B = A ∪ C.
27. The equation x2 = 2x has three real solutions.
28. Suppose a, b ∈ Z. If a | b and b | a, then a = b.
29. If x, y ∈ R and |x + y| = |x − y|, then y = 0.
30. There exist integers a and b for which 42a + 7b = 1.
31. No number (other than 1) appears in Pascal’s triangle more than four times.
32.
¡ n ¢
If n, k ∈ N and k is a prime number, then k = 1 or k = n − 1.
33. Suppose f (x) = a0 + a1x + a2x2 + ··· + anxn is a polynomial of degree 1 or greater,
and for which each coefficient ai is in N. Then there is an n ∈ N for which the
integer f (n) is not prime.
34. If X ⊆ A ∪ B, then X ⊆ A or X ⊆ B.
CHAPTER
10
Mathematical Induction
his chapter explains a powerful proof technique called mathematical
T induction (or just induction for short). To motivate the discussion,
let’s first examine the kinds of statements that induction is used to prove.
Consider the following statement.
Conjecture. The sum of the first n odd natural numbers equals n2.
The following table illustrates what this conjecture says. Each row
is headed by a natural number n, followed by the sum of the first n odd
natural numbers, followed by n2.
n
sum of the first n odd natural numbers
n2
1
1 = . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2
1 + 3 = . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
3
1 + 3 + 5 = . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
4
1 + 3 + 5 + 7 = . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
5
1 + 3 + 5 + 7 + 9 = . . . . . . . . . . . . . . . . . . . . . . . .
25
..
.
.
.
..
..
n
1 + 3 + 5 + 7 + 9 + 11 + ··· + (2n − 1) = . . . . . . .
n2
..
.
.
.
..
..
Note that in the first five lines of the table, the sum of the first n odd
numbers really does add up to n2. Notice also that these first five lines
indicate that the nth odd natural number (the last number in each sum)
is 2n − 1. (For instance, when n = 2, the second odd natural number is
2 · 2 − 1 = 3; when n = 3, the third odd natural number is 2 · 3 − 1 = 5, etc.)
The table raises a question. Does the sum 1+3+5+7+· · ·+(2n −1) really
always equal n2? In other words, is the conjecture true?
Let’s rephrase this as follows. For each natural number n (i.e., for each
line of the table), we have a statement Sn, as follows:
155
S1 : 1 = 12
S2 : 1 + 3 = 22
S3 : 1 + 3 + 5 = 32
...
Sn : 1 + 3 + 5 + 7 + ··· + (2n − 1) = n2
...
Our question is: Are all of these statements true?
Mathematical induction is designed to answer just this kind of question.
It is used when we have a set of statements S1, S2, S3, . . . , Sn, . . ., and we
need to prove that they are all true. The method is really quite simple.
To visualize it, think of the statements as dominoes, lined up in a row.
Imagine you can prove the first statement S1, and symbolize this as
domino S1 being knocked down. Additionally, imagine that you can prove
that any statement Sk being true (falling) forces the next statement Sk+1
to be true (to fall). Then S1 falls, and knocks down S2. Next S2 falls and
knocks down S3, then S3 knocks down S4, and so on. The inescapable
conclusion is that all the statements are knocked down (proved true).
The Simple Idea Behind Mathematical Induction
S1
S2
S3
S4
S5
S6
· · ·
Sk
Sk+1
Sk+2
Sk+3
Sk+4 ···
Statements are lined up like dominoes.
S1
S2
S3
S4
S5
S6
· · ·
Sk
Sk+1
Sk+2
Sk+3
Sk+4 ···
(1) Suppose the first statement falls (i.e. is proved true);
S
S
S
S
S
S
S
· · ·
k
Sk+1 S
S
S
· · ·
1
2
3
4
5
6
k+2
k+3
k+4
(2) Suppose the kth falling always causes the (k + 1)th to fall;
S
S
S
S
S
S
S
S
S
S
1
2
3
4
5
6
k
k+
k
k
· · ·
1
+2
+3
· · ·
Then all must fall (i.e. all statements are proved true).
156
Mathematical Induction
This picture gives our outline for proof by mathematical induction.
Outline for Proof by Induction
Proposition
The statements S1, S2, S3, S4, . . . are all true.
Proof. (Induction)
(1) Prove that the first statement S1 is true.
(2) Given any integer k ≥ 1, prove that the statement Sk ⇒ Sk+1 is true.
It follows by mathematical induction that every Sn is true.
■
In this setup, the first step (1) is called the basis step. Because S1 is
usually a very simple statement, the basis step is often quite easy to do.
The second step (2) is called the inductive step. In the inductive step
direct proof is most often used to prove Sk ⇒ Sk+1, so this step is usually
carried out by assuming Sk is true and showing this forces Sk+1 to be true.
The assumption that Sk is true is called the inductive hypothesis.
Now let’s apply this technique to our original conjecture that the sum
of the first n odd natural numbers equals n2. Our goal is to show that for
each n ∈ N, the statement Sn : 1 + 3 + 5 + 7 + · · · + (2n − 1) = n2 is true. Before
getting started, observe that Sk is obtained from Sn by plugging k in for n.
Thus Sk is the statement Sk : 1+3+5+7+· · ·+(2k −1) = k2. Also, we get Sk+1
by plugging in k +1 for n, so that Sk+1 : 1+3+5+7+· · ·+(2(k +1)−1) = (k +1)2.
Proposition
If n ∈ N, then 1 + 3 + 5 + 7 + · · · + (2n − 1) = n2.
Proof. We will prove this with mathematical induction.
(1) Observe that if n = 1, this statement is 1 = 12, which is obviously true.
(2) We must now prove Sk ⇒ Sk+1 for any k ≥ 1. That is, we must show
that if 1+3+5+7+· · ·+(2k−1) = k2, then 1+3+5+7+· · ·+(2(k+1)−1) = (k+1)2.
We use direct proof. Suppose 1 + 3 + 5 + 7 + · · · + (2k − 1) = k2. Then
1 + 3 + 5 + 7 + ··············· + (2(k + 1) − 1) =
1 + 3 + 5 + 7 + ··· + (2k − 1) + (2(k + 1) − 1) =
¡1 + 3 + 5 + 7 + ··· + (2k − 1)¢ + (2(k + 1) − 1) =
k2 + (2(k + 1) − 1) = k2 + 2k + 1
= (k + 1)2.
Thus 1 + 3 + 5 + 7 + · · · + (2(k + 1) − 1) = (k + 1)2. This proves that Sk ⇒ Sk+1.
It follows by induction that 1 + 3 + 5 + 7 + · · · + (2n − 1) = n2 for every n ∈ N.
■
157
In induction proofs it is usually the case that the first statement
S1 is indexed by the natural number 1, but this need not always be so.
Depending on the problem, the first statement could be S0, or Sm for any
other integer m. In the next example the statements are S0, S1, S2, S3, . . .
The same outline is used, except that the basis step verifies S0, not S1.
Proposition
If n is a non-negative integer, then 5 | (n5 − n).
Proof. We will prove this with mathematical induction. Observe that the
first non-negative integer is 0, so the basis step involves n = 0.
(1) If n = 0, this statement is 5 | (05 − 0) or 5 | 0, which is obviously true.
(2) Let k ≥ 0. We need to prove that if 5 | (k5 − k), then 5 | ((k + 1)5 − (k + 1)).
We use direct proof. Suppose 5 | (k5 − k). Thus k5 − k = 5a for some a ∈ Z.
Observe that
(k + 1)5 − (k + 1) = k5 + 5k4 + 10k3 + 10k2 + 5k + 1 − k − 1
= (k5 − k) + 5k4 + 1
0k3 + 10k2 + 5k
= 5a + 5k4 + 10k3 + 10k2 + 5k
= 5(a + k4 + 2k3 + 2k2 + k).
This shows (k+1)5 −(k+1) is an integer multiple of 5, so 5 | ((k+1)5 −(k+1)).
We have now shown that 5 | (k5 − k) implies 5 | ((k + 1)5 − (k + 1)).
It follows by induction that 5 | (n5 − n) for all non-negative integers n.
■
As noted, induction is used to prove statements of the form ∀ n ∈ N, Sn.
But notice the outline does not work for statements of form ∀ n ∈ Z, Sn
(where n is in Z, not N). The reason is that if you are trying to prove
∀ n ∈ Z, Sn by induction, and you’ve shown S1 is true and Sk ⇒ Sk+1, then
it only follows from this that Sn is true for n ≥ 1. You haven’t proved
that any of the statements S0, S−1, S−2, . . . are true. If you ever want to
prove ∀ n ∈ Z, Sn by induction, you have to show that some Sa is true and
Sk ⇒ Sk+1 and Sk ⇒ Sk−1.
Unfortunately, the term mathematical induction is sometimes confused
with inductive reasoning, that is, the process of reaching the conclusion
that something is likely to be true based on prior observations of similar
circumstances. Please note that that mathematical induction, as intro-
duced here, is a rigorous method that proves statements with absolute
certainty.
158
Mathematical Induction
To round out this section, we present four additional induction proofs.
n
Proposition
X
If n ∈ Z and n ≥ 0, then
i · i! = (n + 1)! − 1.
i=0
Proof. We will prove this with mathematical induction.
(1) If n = 0, this statement is
0
X i · i! = (0 + 1)! − 1.
i=0
Since the left-hand side is 0 · 0! = 0, and the right-hand side is 1! − 1 = 0,
P0
the equation
i
i
· i! = (0 + 1)! − 1
=0
holds, as both sides are zero.
(2) Consider any integer k ≥ 0. We must show that Sk implies Sk+1. That
is, we must show that
k
X i · i! = (k + 1)! − 1
i=0
implies
k+1
X i · i! = ((k + 1) + 1)! − 1.
i=0
k
X
We use direct proof. Suppose
i · i! = (k + 1)! − 1. Observe that
i=0
k+1
à k
!
X i
X
· i! =
i · i! + (k + 1)(k + 1)!
i=0
i=0
³
´
=
(k + 1)! − 1 + (k + 1)(k + 1)!
= (k + 1)! + (k + 1)(k + 1)! − 1
= ¡1 + (k + 1)¢(k + 1)! − 1
= (k + 2)(k + 1)! − 1
Book of Proof Page 22