Some claims are easy once you know whether is even or odd, but you are not told which. How can a proof use a fact it does not have?

Discrete Mathematics and Proof

Proof by cases

Some claims are easy once you know whether n is even or odd, but you are not told which. How can a proof use a fact it does not have?

You need

Proving statements about even and odd numbersDiscrete Mathematics and Proof Direct proofGrades 9 to 12

Where you are 14 in Proof techniques

Logic, proof and discrete math6

Proof techniques14

▴ 6 above Writing a proof as prose Existence proof

Proof by cases

Proof by contraposition The pigeonhole principle ▾ Show all 14 (3 more)

When you reach for it

You reach for cases when a claim would be easy if you knew one more fact, and every possible value of that fact can be handled. For an integer n you do not know whether n is even or odd, but you know it is one of the two, so you prove the claim for even n, then for odd n, and you are done. In logical form: if at least one of Q_1, Q_2, \ldots, Q_m is true, and each Q_i \to P is proved, then P is true.

This lesson takes two days. Part 1 splits by parity, for one integer and for two, and shows how symmetry shortens a split. Part 2 splits by remainders on division by 3 and by the sign of a real number.

The procedure

Part 1: splitting by parity

A proof by cases makes three promises, and each one has a reason behind it.

The cases cover every possibility. This is the step that makes the method valid. If some integer fell in no case, nothing would have been proved about it. Parity is the standard split because Proving statements about even and odd numbers proved that every integer is even or odd. Coverage is all that is needed: cases may overlap, and that does no harm, as long as nothing falls outside all of them.

Each case is a full proof. Inside a case you gain one assumption, such as “n is even”, and you unpack it exactly as in a direct proof: n = 2k for some integer k. A case may cite the parity rules for sums and products from Proving statements about even and odd numbers. It may not borrow anything from the other case.

A closing sentence joins them. After the last case, one sentence says that the claim holds in every case and that the cases cover everything, so the claim holds. This is the sentence that turns several conditional results into the original claim, and it is where a proof ends.

Two letters, four cases, and symmetry. A claim about two integers a and b may need the parity of both, which gives four cases: even and even, even and odd, odd and even, odd and odd. Often two of them are the same argument with the letters exchanged. The phrase “without loss of generality” announces that the proof will write out only one of them. It is honest only when swapping a and b turns the claim, its hypotheses included, into the very same claim. Then any pair (a, b) in the skipped case becomes a pair in the written case once the names are exchanged, and the written proof applies to it. If the claim changes under the swap, the skipped case is a different claim and must be proved on its own.

Part 2: cases beyond parity

Remainders on division by 3. Every integer can be written as exactly one of 3k, 3k + 1 or 3k + 2 for some integer k. This is the case b = 3 of the division algorithm, stated here without proof; it is proved later in the course. The same fact says that a number of the form 3m + 1 or 3m + 2 is not a multiple of 3, since its remainder is not 0. Any divisor works the same way: dividing by 5 gives five cases, 5k through 5k + 4.

Figure 1Every integer has remainder 0, 1 or 2 on division by 3, so the forms 3k, 3k + 1 and 3k + 2 cover \mathbb{Z}.

Signs of real numbers. The absolute value is defined by cases:

\lvert x \rvert = \begin{cases} x & \text{if } x \ge 0, \\ -x & \text{if } x < 0. \end{cases}

So any claim about \lvert x \rvert is proved by splitting on the sign of x, and these two cases cover every real number. One remark saves work: \lvert t \rvert = -t holds for every t \le 0, including t = 0, since \lvert 0 \rvert = 0 = -0. The larger and smaller of two numbers, \max(x, y) and \min(x, y), are also defined by cases: if x \le y, then \max(x, y) = y and \min(x, y) = x, and otherwise the other way round. When x = y both equal x.

Worked examples

Examples 1 to 3 go with Part 1, and Examples 4 to 7 with Part 2.

Example 1

Two parity cases

Prove that n^3 + n is even for every integer n.

Solution

Proof. Let n be an integer. Every integer is even or odd, so there are two cases.

Case 1: n is even. Then n = 2k for some integer k, and

n^3 + n = 8k^3 + 2k = 2(4k^3 + k).

Since 4k^3 + k is an integer, n^3 + n is even.

Case 2: n is odd. Then n = 2k + 1 for some integer k, and

\begin{aligned} n^3 + n &= (8k^3 + 12k^2 + 6k + 1) + (2k + 1) \\ &= 2(4k^3 + 6k^2 + 4k + 1). \end{aligned}

Since 4k^3 + 6k^2 + 4k + 1 is an integer, n^3 + n is even.

In both cases n^3 + n is even, and every integer falls in one of them, so n^3 + n is even for every integer n. \square

Check at n = -3: -27 - 3 = -30, even. The parity rules also give a one-line proof, since n^3 and n have the same parity, so their sum is even. The cases are worth seeing here because the next examples have no such shortcut.

Example 2

Four cases cut to three

Prove that (a + 1)(b + 1)(a + b) is even for all integers a and b.

Solution

A product is even as soon as one factor is even (Theorem 3 of Proving statements about even and odd numbers), so in each case it is enough to find one even factor. Which factor is even depends on the parities of both letters, so there are four cases, shown in the grid.

Figure 2The four parity cases for (a + 1)(b + 1)(a + b), each naming its even factor. The shaded case, a odd and b even, is the case a even and b odd with the letters swapped.

The expression is symmetric: exchanging a and b gives (b + 1)(a + 1)(b + a), which is the same number by the commutative properties of addition and multiplication. So the case “a odd, b even” is the case “a even, b odd” with the names exchanged, and three cases are enough.

Proof. Let a and b be integers.

Case 1: both are even. Then a + b is even, as a sum of two evens.

Case 2: both are odd. Then a + 1 is even, as a sum of two odds.

Case 3: one is even and one is odd. Since the expression is unchanged when a and b are exchanged, we may assume without loss of generality that a is even and b is odd. Then b + 1 is even.

In every case one factor is even, so the product is even. The three cases cover all pairs of integers, so (a + 1)(b + 1)(a + b) is even for all integers a and b. \square

Check at a = 2, b = 5: 3 \cdot 6 \cdot 7 = 126, even.

Example 3

A function defined by cases

Define f on the integers by f(n) = n + 1 when n is even and f(n) = n - 1 when n is odd. Prove that f(f(n)) = n for every integer n.

Solution

The rule for f is itself a split by parity, so the proof splits the same way. The second time f is applied, its rule depends on the parity of f(n), which each case has to work out.

Proof. Let n be an integer.

Case 1: n is even. Then f(n) = n + 1. An even number plus 1 is odd, so f applied to n + 1 uses its second rule: f(n + 1) = (n + 1) - 1 = n.

Case 2: n is odd. Then f(n) = n - 1, which is even, as odd minus odd. So f(n - 1) = (n - 1) + 1 = n.

In both cases f(f(n)) = n, and every integer is even or odd. \square

For example f(6) = 7 and f(7) = 6, and f(-3) = -4 and f(-4) = -3. The function swaps 0 with 1, 2 with 3, and so on.

Example 4

Squares on division by 3

Prove that every perfect square leaves remainder 0 or 1 on division by 3.

Solution

Proof. Let n be an integer. Then n = 3k, n = 3k + 1 or n = 3k + 2 for some integer k.

Case 1: n = 3k. Then n^2 = 9k^2 = 3(3k^2), remainder 0.

Case 2: n = 3k + 1. Then n^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1, remainder 1.

Case 3: n = 3k + 2. Then

n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1,

remainder 1.

The three cases cover every integer, so n^2 always leaves remainder 0 or 1. \square

The proof shows more: the remainder is 0 exactly when 3 \mid n. Check: 5^2 = 25 = 3 \cdot 8 + 1 and 6^2 = 36 = 3 \cdot 12. A consequence is that no square has the form 3m + 2, so for instance 3{,}332, which is 3 \cdot 1{,}110 + 2, is not a perfect square.

Example 5

Signs and absolute value

Prove that \lvert xy \rvert = \lvert x \rvert \lvert y \rvert for all real numbers x and y.

Solution

Each absolute value is unpacked by the sign of what is inside it, so the cases are the four sign patterns of x and y. The claim is symmetric in x and y (since xy = yx), so the two mixed patterns are one case.

Proof. Let x and y be real numbers.

Case 1: x \ge 0 and y \ge 0. Then xy \ge 0, so \lvert xy \rvert = xy = \lvert x \rvert \lvert y \rvert.

Case 2: x < 0 and y < 0. Then xy > 0, so \lvert xy \rvert = xy = (-x)(-y) = \lvert x \rvert \lvert y \rvert.

Case 3: one of them is negative and the other is not. By symmetry we may assume without loss of generality that x \ge 0 and y < 0. Then xy \le 0, so \lvert xy \rvert = -xy, using the remark that \lvert t \rvert = -t for every t \le 0. And \lvert x \rvert \lvert y \rvert = x(-y) = -xy.

The three cases cover every pair of real numbers, so \lvert xy \rvert = \lvert x \rvert \lvert y \rvert always. \square

The remark about t \le 0 is what lets Case 3 include x = 0. Without it, x = 0 would need a case of its own. Check: x = 4, y = -5 gives \lvert -20 \rvert = 20 = 4 \cdot 5.

Example 6

The larger and the smaller

Prove that for all real numbers x and y,

\begin{aligned} \max(x, y) + \min(x, y) &= x + y, \\ \max(x, y) - \min(x, y) &= \lvert x - y \rvert. \end{aligned}

Then solve for \max(x, y).

Solution

Proof. Swapping x and y changes none of \max(x, y), \min(x, y) or x + y, and \lvert y - x \rvert = \lvert -(x - y) \rvert = \lvert x - y \rvert by the previous example with the first factor -1. So both equations are unchanged by the swap, and we may assume without loss of generality that x \le y.

Then \max(x, y) = y and \min(x, y) = x, so the sum is y + x = x + y. Since x - y \le 0, \lvert x - y \rvert = -(x - y) = y - x, which is the difference y - x. \square

Adding the two equations gives 2\max(x, y) = x + y + \lvert x - y \rvert, so

\max(x, y) = \frac{x + y + \lvert x - y \rvert}{2}.

Check at x = 3, y = -5: the formula gives \displaystyle \frac{-2 + 8}{2} = 3, which is the larger number. The formula has no cases in it: the absolute value has absorbed them.

Example 7

Remainders of two squares

Prove that if 3 \mid a^2 + b^2 for integers a and b, then 3 \mid a and 3 \mid b.

Solution

The cases come from Example 4, which says each square is 3j when the number is a multiple of 3 and 3j + 1 when it is not.

Proof. Let a and b be integers with 3 \mid a^2 + b^2. Every pair falls in one of three cases, depending on how many of a and b are multiples of 3.

Case 1: neither is. By Example 4, a^2 = 3s + 1 and b^2 = 3t + 1 for integers s and t, so a^2 + b^2 = 3(s + t) + 2. This has remainder 2, so it is not a multiple of 3, against the hypothesis. This case cannot occur.

Case 2: exactly one is. The hypothesis is symmetric in a and b, so without loss of generality 3 \mid a and 3 \nmid b. Then a^2 = 3s and b^2 = 3t + 1, so a^2 + b^2 = 3(s + t) + 1, again not a multiple of 3. This case cannot occur either.

Case 3: both are. This is the conclusion.

The cases cover every pair, and the first two are impossible, so 3 \mid a and 3 \mid b. \square

Here two cases end not in the claim but in a contradiction with the hypothesis, which also closes them. It follows that 9 \mid a^2 + b^2 whenever 3 divides it: with a = 3c and b = 3d, the sum is 9(c^2 + d^2). Check: 3^2 + 6^2 = 45 = 9 \cdot 5, while 1^2 + 2^2 = 5 is not a multiple of 3.

Boundaries

The cases must cover everything the claim is about. A proof with a gap proves nothing about the values in the gap. Splitting the reals into x > 0 and x < 0 misses x = 0. Splitting the integers into 3k and 3k + 1 misses 3k + 2, and Exercise 18 shows a false claim slipping through that way.

Without loss of generality needs a real symmetry. The claim, its hypotheses included, must be unchanged when the letters are exchanged. If it is not, the skipped case is a different statement (Exercise 19).

Each case may use only its own assumption. A fact found in Case 1 is not available in Case 2.

The number of cases grows fast. Two integers split by parity give four cases, and three give eight. Division by 5 gives five cases for one integer and twenty-five for two. Symmetry and results already proved (such as Example 4) are the usual ways to keep the count small.

Where this goes next

The split by remainder is the start of arithmetic with remainders, where “n has remainder 1 on division by 3” becomes a quantity you can compute with, and of the division algorithm itself. Many statements that look hard to start, such as “if n^2 is even then n is even”, are handled by proof by contraposition, and the two directions of an if and only if often split into cases of their own. The facts about \lvert x \rvert proved here, especially \lvert x + y \rvert \le \lvert x \rvert + \lvert y \rvert, are the working tools of every argument about distance and closeness that follows.

Exercises

Part 1: splitting by parity

Prove by cases that n^2 + 7n + 4 is even for every integer n.
Prove by cases that 5n^2 + 3n + 7 is odd for every integer n. Then give a one-line proof using the parity rules.
Define \displaystyle h(n) = \frac{n}{2} when n is even and \displaystyle h(n) = \frac{n - 1}{2} when n is odd. Prove that h(n) + h(n + 1) = n for every integer n.
For the function f of Example 3, prove that n + f(n) is odd and that f(n + 2) = f(n) + 2 for every integer n.

Part 1: two integers

Prove that (a^2 + b^2)(a + b + 1) is even for all integers a and b, using “without loss of generality” where it is honest.
Prove that if ab is even and a + b is even, then a and b are both even.
Prove that (a - b)(a + b + 1) is even for all integers a and b, using two cases: a and b have the same parity, or they do not.

Part 2: remainders

Prove that 3 \mid n(n^2 + 5) for every integer n.
Prove that 3 \mid 2n^2 + 1 exactly when 3 \nmid n.
Prove that n^2 + n + 1 is a multiple of 3 exactly when n has the form 3k + 1.
Prove that every square leaves remainder 0, 1 or 4 on division by 5, using the cases 5k, 5k \pm 1 and 5k \pm 2. Deduce that n^2 + 2 is never a multiple of 5.

Part 2: sign cases

Prove that \lvert -x \rvert = \lvert x \rvert and \lvert x \rvert^2 = x^2 for every real number x.
Prove that -\lvert x \rvert \le x \le \lvert x \rvert for every real number x.
Prove that \lvert x + y \rvert \le \lvert x \rvert + \lvert y \rvert for all real numbers x and y, by cases on the sign of x + y.
Prove that \displaystyle \min(x, y) = \frac{x + y - \lvert x - y \rvert}{2}.
Prove that \max(x, y) \cdot \min(x, y) = xy.
Solve \lvert x - 2 \rvert + \lvert x + 1 \rvert = 5 by splitting the real line at -1 and 2.

Reasoning

Consider the claim: for every integer n, 3 \nmid n^2 + 2. The case n = 3k gives 9k^2 + 2, remainder 2. Finish the case analysis and decide whether the claim is true.
May a proof of “if a and b have different parities, then a^2 + 3ab + b^2 is odd” say “without loss of generality, a is even and b is odd”? May a proof of “if a and b have different parities, then a + 2b is odd” say the same? Explain.
A proof about real numbers uses the cases x \ge 0 and x \le 0, which overlap at 0. Another uses x > 0 and x < 0. Is each a valid split? Explain.
Use Exercise 14 to prove that \lvert x \rvert - \lvert y \rvert \le \lvert x - y \rvert for all real numbers x and y.

Answers

If n = 2k, then n^2 + 7n + 4 = 4k^2 + 14k + 4 = 2(2k^2 + 7k + 2). If n = 2k + 1, it is 4k^2 + 18k + 12 = 2(2k^2 + 9k + 6). Even in both cases, and every integer is in one.
If n = 2k: 20k^2 + 6k + 7 = 2(10k^2 + 3k + 3) + 1. If n = 2k + 1: 20k^2 + 26k + 15 = 2(10k^2 + 13k + 7) + 1. Odd in both cases. One line: 5n^2 and 3n both have the parity of n, so their sum is even, and even plus 7 is odd.
If n = 2k, then n + 1 is odd, so \displaystyle h(n) + h(n + 1) = k + \frac{2k}{2} = 2k = n. If n = 2k + 1, then n + 1 = 2k + 2 is even, so the sum is k + (k + 1) = 2k + 1 = n.
If n is even, n + f(n) = 2n + 1, odd; if n is odd, n + f(n) = 2n - 1 = 2(n - 1) + 1, odd. Since n + 2 has the parity of n, the same rule applies to both: for even n, f(n + 2) = n + 3 = f(n) + 2, and for odd n, f(n + 2) = n + 1 = f(n) + 2.
Both even or both odd: a^2 + b^2 is even, since a^2 and b^2 have the parities of a and b. One of each: the expression is unchanged by swapping a and b, so without loss of generality a is even and b odd; then a + b is odd and a + b + 1 is even. An even factor in every case.
If both are odd, ab is odd, against the hypothesis. If exactly one is odd (without loss of generality a, since both hypotheses are symmetric), a + b is odd, against the hypothesis. The only case left is that both are even.
Same parity: a - b is even. Different parity: a + b is odd, so a + b + 1 is even. Either way a factor is even, and two integers either have the same parity or do not.
n = 3k: the factor n is 3k. n = 3k + 1: n^2 + 5 = 9k^2 + 6k + 6 = 3(3k^2 + 2k + 2). n = 3k + 2: n^2 + 5 = 9k^2 + 12k + 9 = 3(3k^2 + 4k + 3). In each case 3 divides a factor.
n = 3k: 2n^2 + 1 = 3(6k^2) + 1, not a multiple of 3. n = 3k + 1: 18k^2 + 12k + 3 = 3(6k^2 + 4k + 1). n = 3k + 2: 18k^2 + 24k + 9 = 3(6k^2 + 8k + 3). So 3 \mid 2n^2 + 1 in exactly the two cases where 3 \nmid n.
n = 3k: 9k^2 + 3k + 1 = 3(3k^2 + k) + 1. n = 3k + 1: 9k^2 + 9k + 3 = 3(3k^2 + 3k + 1). n = 3k + 2: 9k^2 + 15k + 7 = 3(3k^2 + 5k + 2) + 1. Only the middle case is a multiple of 3.
The cases cover every integer, since 5k + 3 = 5(k + 1) - 2 and 5k + 4 = 5(k + 1) - 1. (5k)^2 = 5(5k^2); (5k \pm 1)^2 = 5(5k^2 \pm 2k) + 1; (5k \pm 2)^2 = 5(5k^2 \pm 4k) + 4. So n^2 + 2 has the form 5j + 2, 5j + 3 or 5j + 6 = 5(j + 1) + 1, never a multiple of 5.
If x \ge 0, then -x \le 0, so \lvert -x \rvert = -(-x) = x = \lvert x \rvert. If x < 0, then -x > 0, so \lvert -x \rvert = -x = \lvert x \rvert. For the square: x \ge 0 gives \lvert x \rvert^2 = x^2, and x < 0 gives (-x)^2 = x^2.
If x \ge 0: \lvert x \rvert = x, and -\lvert x \rvert = -x \le 0 \le x. If x < 0: -\lvert x \rvert = x, and x < 0 < -x = \lvert x \rvert.
If x + y \ge 0: \lvert x + y \rvert = x + y \le \lvert x \rvert + \lvert y \rvert, adding x \le \lvert x \rvert and y \le \lvert y \rvert from Exercise 13. If x + y < 0: \lvert x + y \rvert = -x - y \le \lvert x \rvert + \lvert y \rvert, since -x \le \lvert x \rvert and -y \le \lvert y \rvert, also from Exercise 13.
Both sides are unchanged by swapping x and y (using \lvert y - x \rvert = \lvert x - y \rvert), so assume x \le y. Then \lvert x - y \rvert = y - x, and the right side is \displaystyle \frac{x + y - y + x}{2} = x = \min(x, y).
Both sides are symmetric, so assume x \le y. Then \max(x, y) \cdot \min(x, y) = yx = xy.
x = -2 or x = 3. For x \ge 2 the equation is (x - 2) + (x + 1) = 2x - 1 = 5, so x = 3, which is in the range. For -1 \le x < 2 it is (2 - x) + (x + 1) = 3, never 5. For x < -1 it is (2 - x) + (-x - 1) = 1 - 2x = 5, so x = -2, which is in the range.
False. For n = 3k + 1, n^2 + 2 = 9k^2 + 6k + 3 = 3(3k^2 + 2k + 1), so n = 1 gives 1 + 2 = 3. (For n = 3k + 2 it is 3(3k^2 + 4k + 2), also a multiple.) Checking one case proved nothing about the others.
The first, yes: swapping a and b gives b^2 + 3ba + a^2, the same number, and the hypothesis is symmetric too. With a even and b odd, a^2 and 3ab are even and b^2 is odd, so the sum is odd. The second, no: the swap gives b + 2a, a different expression, so the two mixed cases are different claims. They also come out differently: a = 1, b = 2 gives 5, odd, while a = 2, b = 1 gives 4, even. The claim is false, and a proof that wrote out only the case “a odd, b even” would seem to prove it.
The first is valid: every real number satisfies x \ge 0 or x \le 0, and overlap only means 0 is proved twice. The second is not: 0 is in neither case, so the claim at x = 0 has not been proved and needs a third case.
Write x = (x - y) + y. By Exercise 14, \lvert x \rvert \le \lvert x - y \rvert + \lvert y \rvert. Subtracting \lvert y \rvert from both sides gives the result.