Proof by Cases

Proving a claim "by cases" is a technique reminiscent of the old adage "Divide and Conquer!". Suppose one is trying to prove some statement $S$. If one knows that one of two or more cases must occur, then one can prove $S$ is true by showing it must be true in each such case. With any luck, each individual case will be more simply argued than attacking the original claim in some other way.

Let us see an example of such an argument:

Suppose one wishes to show that the square of any integer is either of the form $3n$ or $3n+1$.

Another way of saying this is that the remainder upon division by $3$ of any integer squared is either $0$ or $1$. We know that when dividing any number by $3$, the resulting remainder must be either $0$, $1$, or $2$. As such, for any integer $m$, we can find an integer $k$ so that one of the following cases must hold:

$$\begin{align*} m &= 3k\\ m &= 3k+1\\ m &= 3k+2 \end{align*}$$

If we can show that $m^2$ takes the form $3n$ or $3n+1$ for some integer $n$ in each one of these cases, we will have proven our claim. Let us consider each case in turn:

Case 1

If $m = 3k$, then $$\begin{split} m^2 &= 9k^2\\ &= 3(3k^2) \end{split}$$

Letting $n = 3k^2$ and noting $n \in \mathbb{Z}$ by closure, we have $m^2 = 3n$ for some integer $n$.

Case 2

If $m = 3k+1$, then $$\begin{split} m^2 &= (3k+1)^2\\ &= 9k^2 + 6k + 1\\ &= 3(3k^2 + 2k) + 1 \end{split}$$

Letting $n = 3k^2 + 2k$ and noting $n \in \mathbb{Z}$ by closure, we have $m^2 = 3n+1$ for some integer $n$.

Case 3

If $m = 3k+2$, then $$\begin{split} m^2 &= (3k+2)^2\\ &= 9k^2 + 12k + 4\\ &= 9k^2 + 12k + 3 + 1\\ &= 3(3k^2 + 4k + 1) + 1 \end{split}$$

Letting $n = 3k^2 + 4k + 1$ and noting $n \in \mathbb{Z}$ by closure, we have $m^2 = 3n+1$ for some integer $n$.

As $m^2$ takes the form $3n$ or $3n+1$ in each possible case, it must be that the square of every integer $m$ takes the form $3n$ or $3n+1$. This, of course, is what we hoped to show.