Page 114 - Discrete Mathematics and Its Applications

1.8 Proof Methods and Strategy 93

EXHAUSTIVEPROOF Sometheoremscanbeprovedbyexaminingarelativelysmallnumber
of examples. Such proofs are called exhaustive proofs,or proofs by exhaustion because these
proofs proceed by exhausting all possibilities. An exhaustive proof is a special type of proof by
cases where each case involves checking a single example. We now provide some illustrations
of exhaustive proofs.
3
n
EXAMPLE 1 Prove that (n + 1) ≥ 3 if n is a positive integer with n ≤ 4.
3
Solution: We use a proof by exhaustion. We only need verify the inequality (n + 1) ≥ 3 n
1
3
3
n
when n = 1, 2, 3, and 4. For n = 1, we have (n + 1) = 2 = 8 and 3 = 3 = 3; for n = 2,
3
n
3
3
3
2
we have (n + 1) = 3 = 27 and 3 = 3 = 9; for n = 3, we have (n + 1) = 4 = 64 and
4
3
n
n
3
3
3 = 3 = 27; and for n = 4, we have (n + 1) = 5 = 125 and 3 = 3 = 81. In each of
n
3
these four cases, we see that (n + 1) ≥ 3 . We have used the method of exhaustion to prove
n
3
that (n + 1) ≥ 3 if n is a positive integer with n ≤ 4. ▲
EXAMPLE 2 Prove that the only consecutive positive integers not exceeding 100 that are perfect powers are
a
8 and 9. (An integer is a perfect power if it equals n , where a is an integer greater than 1.)
Solution: We use a proof by exhaustion. In particular, we can prove this fact by examining
positive integers n not exceeding 100, first checking whether n is a perfect power, and if it is,
checking whether n + 1 is also a perfect power. A quicker way to do this is simply to look at all
perfect powers not exceeding 100 and checking whether the next largest integer is also a perfect
power. The squares of positive integers not exceeding 100 are 1, 4, 9, 16, 25, 36, 49, 64, 81, and
100. The cubes of positive integers not exceeding 100 are 1, 8, 27, and 64. The fourth powers
of positive integers not exceeding 100 are 1, 16, and 81. The fifth powers of positive integers
not exceeding 100 are 1 and 32. The sixth powers of positive integers not exceeding 100 are 1
and 64. There are no powers of positive integers higher than the sixth power not exceeding 100,
other than 1. Looking at this list of perfect powers not exceeding 100, we see that n = 8isthe
2
3
only perfect power n for which n + 1 is also a perfect power. That is, 2 = 8 and 3 = 9 are the
only two consecutive perfect powers not exceeding 100. ▲
Proofs by exhaustion can
tire out people and People can carry out exhaustive proofs when it is necessary to check only a relatively small
computers when the number of instances of a statement. Computers do not complain when they are asked to check
number of cases a much larger number of instances of a statement, but they still have limitations. Note that not
challenges the available even a computer can check all instances when it is impossible to list all instances to check.
processing power!
PROOF BY CASES A proof by cases must cover all possible cases that arise in a theorem.
We illustrate proof by cases with a couple of examples. In each example, you should check that
all possible cases are covered.
2
EXAMPLE 3 Prove that if n is an integer, then n ≥ n.
2
Solution: We can prove that n ≥ n for every integer by considering three cases, when n = 0,
when n ≥ 1, and when n ≤−1. We split the proof into three cases because it is straightforward
to prove the result by considering zero, positive integers, and negative integers separately.
2
2
2
Case (i): When n = 0, because 0 = 0, we see that 0 ≥ 0. It follows that n ≥ n is true in
this case.
Case (ii): When n ≥ 1, when we multiply both sides of the inequality n ≥ 1 by the positive
2
integer n, we obtain n · n ≥ n · 1. This implies that n ≥ n for n ≥ 1.
2
2
Case (iii): In this case n ≤−1. However, n ≥ 0. It follows that n ≥ n.
2
Because the inequality n ≥ n holds in all three cases, we can conclude that if n is an integer,
2
then n ≥ n. ▲