Page 116 - Discrete Mathematics and Its Applications

1.8 Proof Methods and Strategy 95

2
Case (vi): The final decimal digit of n is 0. Then the final decimal digit of n is the final
2
decimal digit of 0 = 0, namely 0.
2
Because we have considered all six cases, we can conclude that the final decimal digit of n ,
where n is an integer is either 0, 1, 2, 4, 5, 6, or 9. ▲

Sometimes we can eliminate all but a few examples in a proof by cases, as Example 6
illustrates.

2
2
EXAMPLE 6 Show that there are no solutions in integers x and y of x + 3y = 8.
2
Solution: We can quickly reduce a proof to checking just a few simple cases because x > 8
2
when |x|≥ 3 and 3y > 8 when |y|≥ 2. This leaves the cases when x equals −2, −1, 0, 1,
or 2 and y equals −1, 0, or 1. We can finish using an exhaustive proof. To dispense with the
2
remaining cases, we note that possible values for x are 0, 1, and 4, and possible values for 3y 2
2
2
are 0 and 3, and the largest sum of possible values for x and 3y is 7. Consequently, it is
2
2
impossible for x + 3y = 8 to hold when x and y are integers. ▲
WITHOUT LOSS OF GENERALITY In the proof in Example 4, we dismissed case (iii),
where x< 0 and y ≥ 0, because it is the same as case (ii), where x ≥ 0 and y< 0, with the
roles of x and y reversed. To shorten the proof, we could have proved cases (ii) and (iii) together
by assuming, without loss of generality, that x ≥ 0 and y< 0. Implicit in this statement is that
we can complete the case with x< 0 and y ≥ 0 using the same argument as we used for the
case with x ≥ 0 and y< 0, but with the obvious changes.
In general, when the phrase “without loss of generality” is used in a proof (often abbreviated
as WLOG), we assert that by proving one case of a theorem, no additional argument is required
to prove other specified cases. That is, other cases follow by making straightforward changes
to the argument, or by filling in some straightforward initial step. Proofs by cases can often be
made much more efficient when the notion of without loss of generality is employed. Of course,
incorrect use of this principle can lead to unfortunate errors. Sometimes assumptions are made
In a proof by cases be that lead to a loss in generality. Such assumptions can be made that do not take into account
sure not to omit any cases
and check that you have that one case may be substantially different from others. This can lead to an incomplete, and
proved all cases correctly! possibly unsalvageable, proof. In fact, many incorrect proofs of famous theorems turned out
to rely on arguments that used the idea of “without loss of generality” to establish cases that
could not be quickly proved from simpler cases.
We now illustrate a proof where without loss of generality is used effectively together with
other proof techniques.

EXAMPLE 7 Show that if x and y are integers and both xy and x + y are even, then both x and y are even.

Solution: We will use proof by contraposition, the notion of without loss of generality, and proof
by cases. First, suppose that x and y are not both even. That is, assume that x is odd or that y is
odd (or both). Without loss of generality, we assume that x is odd, so that x = 2m + 1 for some
integer k.
To complete the proof, we need to show that xy is odd or x + y is odd. Consider
two cases: (i) y even, and (ii) y odd. In (i), y = 2n for some integer n, so that x + y =
(2m + 1) + 2n = 2(m + n) + 1 is odd. In (ii), y = 2n + 1 for some integer n, so that xy =
(2m + 1)(2n + 1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1 is odd. This completes the
proof by contraposition. (Note that our use of without loss of generality within the proof is
justified because the proof when y is odd can be obtained by simply interchanging the roles of
x and y in the proof we have given.) ▲

COMMON ERRORSWITH EXHAUSTIVE PROOF AND PROOF BY CASES A common
error of reasoning is to draw incorrect conclusions from examples. No matter how many separate
examples are considered, a theorem is not proved by considering examples unless every possible