Page 115 - Discrete Mathematics and Its Applications

94 1 / The Foundations: Logic and Proofs

EXAMPLE 4 Use a proof by cases to show that |xy|=|x||y|, where x and y are real numbers. (Recall that
|a|, the absolute value of a, equals a when a ≥ 0 and equals −a when a ≤ 0.)

Solution: In our proof of this theorem, we remove absolute values using the fact that |a|= a
when a ≥ 0 and |a|=−a when a< 0. Because both |x| and |y| occur in our formula, we will
need four cases: (i) x and y both nonnegative, (ii) x nonnegative and y is negative, (iii) x negative
and y nonnegative, and (iv) x negative and y negative. We denote by p 1 , p 2 , p 3 , and p 4 , the
proposition stating the assumption for each of these four cases, respectively.
(Note that we can remove the absolute value signs by making the appropriate choice of
signs within each case.)
Case (i): We see that p 1 → q because xy ≥ 0 when x ≥ 0 and y ≥ 0, so that |xy|= xy =
|x||y|.
Case (ii): To see that p 2 → q, note that if x ≥ 0 and y< 0, then xy ≤ 0, so that |xy|=
−xy = x(−y) =|x||y|. (Here, because y< 0, we have |y|=−y.)
Case (iii): To see that p 3 → q, we follow the same reasoning as the previous case with the
roles of x and y reversed.
Case (iv): To see that p 4 → q, note that when x< 0 and y< 0, it follows that xy > 0.
Hence, |xy|= xy = (−x)(−y) =|x||y|.

Because |xy|=|x||y| holds in each of the four cases and these cases exhaust all possibilities,
we can conclude that |xy|=|x||y|, whenever x and y are real numbers. ▲

LEVERAGING PROOF BY CASES The examples we have presented illustrating proof by
cases provide some insight into when to use this method of proof. In particular, when it is not
possible to consider all cases of a proof at the same time, a proof by cases should be considered.
When should you use such a proof ? Generally, look for a proof by cases when there is no
obvious way to begin a proof, but when extra information in each case helps move the proof
forward. Example 5 illustrates how the method of proof by cases can be used effectively.
EXAMPLE 5 Formulate a conjecture about the final decimal digit of the square of an integer and prove your
result.
Solution: The smallest perfect squares are 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169,
196, 225, and so on. We notice that the digits that occur as the final digit of a square are
0, 1, 4, 5, 6, and 9, with 2, 3, 7, and 8 never appearing as the final digit of a square.We conjecture
this theorem: The final decimal digit of a perfect square is 0, 1, 4, 5, 6 or 9. How can we prove
this theorem?
We first note that we can express an integer n as 10a + b, where a and b are pos-
itive integers and b is 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9. Here a is the integer obtained by
subtracting the final decimal digit of n from n and dividing by 10. Next, note that
2
2
2
2
2
(10a + b) = 100a + 20ab + b = 10(10a + 2b) + b , so that the final decimal digit of n 2
2
is the same as the final decimal digit of b . Furthermore, note that the final decimal digit of b 2
2
2
is the same as the final decimal digit of (10 − b) = 100 − 20b + b . Consequently, we can
reduce our proof to the consideration of six cases.
2
Case (i): The final digit of n is 1 or 9. Then the final decimal digit of n is the final decimal
2
2
digit of 1 = 1or9 = 81, namely 1.
2
Case (ii): The final digit of n is 2 or 8. Then the final decimal digit of n is the final decimal
2
2
digit of 2 = 4or8 = 64, namely 4.
2
Case (iii): The final digit of n is 3 or 7. Then the final decimal digit of n is the final decimal
2
2
digit of 3 = 9or7 = 49, namely 9.
2
Case (iv): The final digit of n is 4 or 6. Then the final decimal digit of n is the final decimal
2
2
digit of 4 = 16 or 6 = 36, namely 6.
2
Case (v): The final decimal digit of n is 5. Then the final decimal digit of n is the final
2
decimal digit of 5 = 25, namely 5.