Chapter 13 ▶ Proof by cases

Our third method of proof is called proof by cases. Proving something by cases is very similar to proving something by exhaustion.

13.1 Steps

The steps in a proof by cases are similar to those in a proof by exhaustion:

1. Perform a partition of \(P\) into cases.
   Note that a partition of \(P\) into “cases” is similar to the list of possibilities you create for a proof by exhaustion, except that cases are generally more broad (usually containing multiple elements) than each single possibility in a proof by exhaustion.

2. Show that the conjecture is true for each of the cases on your list.
   In a proof by exhaustion, you had to show that the conjecture was true for each possibility, which usually required testing just a single number. Similarly for a proof by cases, you need to show that \(P \rightarrow Q\) for each case, but as cases generally contain more elements, something like a direct proof will be needed for each case.

Here are some examples of how you might split up a proof into cases (Step 1), depending on what type of number the conjecture concerns:

Family	Possible cases
\(a \in \mathbb Z\)	Case 1: \(a\) is even Case 2: \(a\) is odd Case 1: \(a = 3k\) Case 2: \(a = 3k + 1\) Case 3: \(a = 3k + 2\) with \(k \in \mathbb Z\) In other words, every integer is either a multiple of \(3\), one more than a multiple of \(3\), or two more than a multiple of \(3\). Case 1: \(a\) is positive Case 2: \(a\) is negative Case 3: \(a\) = 0
\(a \in \mathbb R\)	Case 1: \(a\) is rational Case 2: \(a\) is irrational Case 1: \(|a| > 1\) Case 2: \(|a| \leq 1\) Case 1: \(a\) is positive Case 2: \(a\) is negative Case 3: \(a\) = 0
Pairs of numbers \(a, b\)	Case 1: both \(a, b > 0\) Case 2: both \(a, b < 0\) Case 3: \(a > 0\) and \(b < 0\) (w.l.o.g.37) Case 4: at least one of \(a\) and \(b\) equals 0 Case 1: \(a,b \neq 0\) Case 2: at least one of \(a\) and \(b\) equals 0

Exercise 13.1 Verify that for each of the examples given in the table above, the cases are distinct and complete (i.e. they form a partition).

Exercise 13.2 Can you think of any other possible cases for the families of numbers in the table?

Note:

• You might partition \(P\) into cases differently to a classmate. Don’t worry! There are many ways to prove the same thing - just make sure you don’t miss any numbers!

• Once you have partitioned \(P\) into cases, consider each case separately from one another.

• For conjectures in this course that require a proof by cases, you will probably need 2, 3, or maybe 4 cases. However, there is no upper limit for how many you can use. Proofs involving between 5 and 10 cases are common. You should always try to use the smallest number of cases possible.³⁸

13.2 Formal definition

To prove “If \(P\) then \(Q\)” by cases, show that

If \(P_1\) then \(Q\).

If \(P_2\) then \(Q\).

\(\vdots\)

If \(P_n\) then \(Q\).

where \(P_1\), \(P_2\), …, \(P_n\) is a partition of \(P\).

13.3 Exhaustion versus cases

Let’s compare a couple of conjectures we previously proved by exhaustion and a couple which can be proved using cases, to see the difference between “possibilities” in a proof by exhaustion and “cases” in a proof by cases.

Conjecture	Proof by exhaustion	Proof by cases
Conjecture 11.4 (from Chapter 11)	The video solution identified four possible divisors of \(97\) (using some clever reasoning about prime numbers and the square root of \(97\) to not identify more possibilities than necessary) and then checked them all. Finding none divided \(97\), and being satisfied that this list of candidate divisors was complete, the conjecture was declared true. List of possibilities: \(2, 3, 5, 7\).
Conjecture 11.3 (from Chapter 11)	In the video solution, the list of possibilities was identified as the integers \(0, 1, 2, 3, ..., 9\). Again, this list was long enough to ensure completeness but not longer than it needed to be. List of possibilities: \(0,1,2,3,4,5,6,7,8,9\).
Conjecture 13.1 : Integers retain their parity when squared.		We should first check the conjecture is true for even integers, then check it’s true for odd integers. Partition of \(a \in \mathbb Z\) into cases: Case 1: All even integers. Case 2: All odd integers.
Conjecture 13.2 : There is no integer \(a\) such that \(a^2 + a^3 = 100\).		Partition of \(a \in \mathbb Z\) into cases: Case 1: \(a \in \mathbb Z^-\) Case 2: \(a=0\) Case 3: \(1 \leq a \leq 4\) Case 4: \(a \geq 5\)
Conjecture 13.3 : For \(a, b \in \mathbb R\), \(|a + b| \leq |a| + |b|\).		As we’re dealing with the modulus function39, it makes sense to build cases by varying the sign of \(a\) and \(b\). Partition of \(a \in \mathbb R\) into cases: Case 1: \(a\) and \(b\) both \(\geq 0\). Case 2: \(a\) and \(b\) both \(< 0\). Case 3: \(a \geq 0\), \(b <0\), \(|a| \geq |b|\). Case 4: \(a \geq 0\), \(b <0\), \(|a| < |b|\).
Conjecture 13.4 : All perfect squares are either a multiple of \(3\) or one more than a multiple of \(3\).		See Exercise 13.3 below.

Exercise 13.3 What do you think for Conjecture 13.4? What cases should we use?

Solution: See below for my suggestion of cases for this conjecture.

13.4 Conjectures

Exercise 13.4 We have already met the following four conjectures above. Use them to practice the method of proof by cases. Solutions are below, as usual.

Conjecture 13.1 : Integers retain their parity when squared.

Conjecture 13.2 : There is no integer \(a\) such that \(a^2 + a^3 = 100\).

Conjecture 13.3 : For \(a, b \in \mathbb R\), \(|a + b| \leq |a| + |b|\).

Conjecture 13.4 : All perfect squares are either a multiple of \(3\) or one more than a multiple of \(3\).

Also, watch 0:00-9:30 of this video for a couple more examples of proof by cases: https://www.youtube.com/watch?v=dheuJkuSNyI.

---

Solutions:

---

Conjecture 13.1: First, we rewrite the conjecture,

If \(a\) is an even integer, then \(a^2\) is an even integer.
If \(a\) is an odd integer, then \(a^2\) is an odd integer.

Now we’re ready for a proof by cases. We’ll use a direct proof within each of the two cases.

Proof.
Case 1: \(a\) even

Since \(a\) is even, it can be written as \[\begin{align} a &= 2k \end{align}\] where \(k\) is an integer.

Then, \[\begin{align} a^2 &= (2k)^2 \\ &= 4k^2 \\ &= 2(2k^2) \end{align}\] by factoring out \(2\).

\(2k^2\) is clearly an integer. Let’s call it \(m\). Therefore we have \[\begin{align} a^2 &= 2m \end{align}\] which is clearly even.

Case 2: \(a\) odd

Since \(a\) is odd, it can be written as \[\begin{align} a &= 2k + 1 \end{align}\] where \(k\) is an integer. (Note that we are allowed to reuse the letter \(k\) as cases are separate from one another.)

Then, \[\begin{align} a^2 &= (2k + 1)^2 \\ &= 4k^2 + 4k + 1 \\ &= 2(2k^2 + 2k) + 1 \end{align}\] by factoring out \(2\).

\(2k^2 + 2k\) is clearly an integer. Let’s call it \(m\). Therefore we have \[\begin{align} a^2 &= 2m + 1 \end{align}\] which is clearly odd.

---

Conjecture 13.2: First, we rewrite the conjecture,

If \(a \in \mathbb Z\), then \(a^2 + a^3 \neq 100\).

Now we’re ready for a proof by cases.

Proof.
Case 1: \(a \in \mathbb Z^-\)
For all negative integers \(a^2 + a^3 \leq 0\), as \(|a^3| \geq |a^2|\) and \(a^3 < 0\).

Case 2: \(a=0\)
\(0^2 + 0^3 = 0 \neq 100\).

Case 3: \(1 \leq a \leq 4\)
We’ll use proof by exhaustion for these four possibilities.

If \(a=1\) then \(a^2 + a^3 = 2 \neq 100\).
If \(a=2\) then \(a^2 + a^3 = 12 \neq 100\).
If \(a=3\) then \(a^2 + a^3 = 36 \neq 100\).
If \(a=4\) then \(a^2 + a^3 = 80 \neq 100\).

Case 4: \(a \geq 5\)
As \(5^2 + 5^3 = 150 > 100\), all integers from \(5\) and up will be too large for \(a^2 + a^3\) to equal \(100\).

---

Conjecture 13.3: First, we rewrite the conjecture,

If \(a, b \in \mathbb R\), then \(|a + b| \leq |a| + |b|\).

Now we’re ready for a proof by cases.

Proof.
Case 1: \(a\) and \(b\) both \(\geq 0\)
Since \(a,b \geq 0\), we know that \(|a| = a\) and \(|b| = b\). Also, as \(a+b \geq 0\), we know that \(|a+b| = a+b\). We have, \[\begin{align} |a + b| &= a + b \end{align}\] and \[\begin{align} |a| + |b| &= a + b \end{align}\] Therefore \(|a + b| = |a| + |b|\), which satisfies the conjecture.

Case 2: \(a\) and \(b\) both \(< 0\)
Since \(a,b <0\), we know that \(|a| = -a\) and \(|b| = -b\). Also, as \(a+b <0\), we know that \(|a+b| = -(a+b)\). We have, \[\begin{align} |a + b| &= -(a + b) \\ &= -a - b \end{align}\] and \[\begin{align} |a| + |b| &= -a - b \end{align}\] Therefore \(|a + b| = |a| + |b|\), which satisfies the conjecture.

Case 3: \(a \geq 0\), \(b <0\), \(|a| \geq |b|\)
Since \(a \geq 0\), \(|a| = a\). Since \(b<0\), we know that \(|b| > 0\).

Thus \[\begin{align} |a| + |b| &> a \end{align}\]

As \(b<0\) and \(|a| \geq |b|\), we know that \[\begin{align} |a + b| &< a \end{align}\] Therefore \(|a + b| < a < |a| + |b|\), which satisfies the conjecture.

Case 4: \(a \geq 0\), \(b <0\), \(|a| < |b|\)
Since \(a \geq 0\), \(|a| = a\). Since \(b<0\), \(|b| = -b\).

Therefore \[\begin{align} |a| + |b| &= a - b \end{align}\]

As \(b<0\) and \(|a| < |b|\), we know that \(a + b < 0\) and thus \[\begin{align} |a + b| &= -(a+b) \\ &= -a-b \end{align}\] The conjecture says that \(|a + b| \leq |a| + |b|\), so we must show that \[\begin{align} -a-b &\leq a - b \end{align}\] Adding \(b\) to both sides gives \(-a \leq a\) which, as \(a \geq 0\), is clearly true.

---

Conjecture 13.4: First, we rewrite the conjecture,

If \(a\) is a perfect square, then \(a\) is either a multiple of \(3\) or one more than a multiple of \(3\).

Now we’re ready for a proof by cases.

Proof. If \(a\) is a perfect square, then there is some integer that when squared gives \(a\). As all integers are either a multiple of \(3\), one more than a multiple of \(3\) or two more than a multiple of \(3\), I’ll consider these three cases. We’ll use a direct proof within each case.

Case 1: \(a=(3n)^2, n \in \mathbb Z\)
i.e. \(a\) is the square of a multiple of \(3\), which covers square numbers like 0, 9, 36, 81, 144, …

We have \[\begin{align} a &= (3n)^2 \\ &= 9n^2 \\ &= 3(3n^2) \end{align}\] which is clearly a multiple of 3.

Case 2: \(a=(3n + 1)^2, n \in \mathbb Z\)
i.e. \(a\) is the square of one more than a multiple of \(3\), which covers square numbers like 1, 16, 49, 100, 169, …

We have \[\begin{align} a &= (3n+1)^2 \\ &= 9n^2 + 6n + 1 \\ &= 3(3n^2 + 2n) + 1 \end{align}\] which is clearly one more than a multiple of 3.

Case 3: \(a=(3n + 2)^2, n \in \mathbb Z\)
i.e. \(a\) is the square of two more than a multiple of \(3\), which covers the remaining square numbers, like 4, 25, 64, 121, 196, …

We have \[\begin{align} a &= (3n+2)^2 \\ &= 9n^2 + 12n + 4 \\ &= 9n^2 + 12n + 3 + 1 \\ &= 3(3n^2 + 4n + 1) + 1 \end{align}\] which is clearly one more than a multiple of 3.

As we’ve accounted for all square numbers, we’re done.

---

Exercise 13.5 Before moving forward, read Chapter 14, Without loss of generality. This is a really useful technique that can save you a lot of time when using proof by cases.

Exercise 13.6 Some of these conjectures are false; disprove them by finding a counterexample. Some of them are true; prove them using one (or a combination of more than one) of the methods we’ve met so far.

Conjecture 13.5 : \(5a+6\) has the same parity as \(a\).

Conjecture 13.6 : \(a^2 + a^3\) is even for all integers \(a\).

Conjecture 13.7 : If \(a\) and \(b\) are integers, \(a^2b^2\) is even.

Conjecture 13.8 : For all numbers \(a, b, c\), if \(ab = bc\) then \(a = c\).

Conjecture 13.9 : For any integer \(a\), \((3a-1)\) is a multiple of \(2\).

Conjecture 13.10 : The sum of two consecutive integers is odd.

Conjecture 13.11 : Let \(a\) be an integer. Then \(a^{2} + a\) is even.

Conjecture 13.12 : There are no negative square numbers.

Conjecture 13.13 : If \(a\) is prime, then \(a + 13\) isn’t.

Conjecture 13.14 : There is no two-digit prime number (with different digits) which is still prime when you swap its digits.

Conjecture 9.1 : For \(a \in \mathbb Z^+\), \(a^2 - a + 11\) is prime.

Conjecture 13.15 : Zero is even.

Conjecture 13.16 : For any pair of integers \(a\) and \(b\), there is an integer \(c\) such that \(a^2 + b^2 = c^2\), where \(c > a\) and \(c > b\).

Conjecture 13.17 : MAX(\(a, b\)) + MIN(\(a, b) = a + b\) for any \(a\) and \(b\).

Conjecture 13.18 : If \(a>c\) and \(b>c\) for any numbers \(a,b\) and \(c\), then MAX\((a,b) - c\) is always positive.

Conjecture 13.19 : Let \(a\) be an integer. If 3 does not divide \(a\), then 3 does divide \(a^2 - 1\).

Conjecture 13.20 : If \(a\) and \(b\) are both positive integers and \(n = ab\), then either \(a \leq \sqrt{n}\) or \(b\leq \sqrt{n}\).

Conjecture 13.21 : The only way for \(3a^2 + 4a + 3\) to be even is if \(a\) is odd.

Conjecture 13.22 : For integers \(a\), \(b\), \(c\), \(d\) and \(n\), \((an + b)\) and \((cn + d)\) have different parity to one another only when \(a\) and \(b\) have different parity to one another AND \(c\) and \(d\) have different parity to one another.

Conjecture 13.23 : 127 is prime.

Conjecture 13.24 : If \(a\) is an integer, then \(a^2 + 1\) is prime.

Conjecture 13.25 : If \(a > 0\), then \(\sqrt a < a\).

---

37. See Chapter 14 for more on w.l.o.g.↩︎

38. The first proof of the Four Colour Theorem used 1936 cases. Since then, mathematicians have managed to reduce this number to close to 600, which is still a lot, but less than 1936!
    The Four Colour Theorem states that any map, like a map of the states of the U.S. or countries of the world, can be coloured using only four colours in such a way that regions sharing a common boundary (other than a single point) do not share the same colour. In other words, a cartographer knows that she needs only four colours to colour any map. See https://www.cantorsparadise.com/the-four-color-theorem-8eece6ab6b12.↩︎

39. Recall the modulus function: \(|a| = a\) for \(a \geq 0\), and \(|a| = -a\) for \(a < 0\).↩︎