Proof by exhaustion tests all possible cases to see if the statement you want to prove is true for all cases.

All cases must be true for this method to work. This method is suited for questions where there are a small number of cases to test.

Proof by exhaustion involves:

1. List all the cases that exhausts all possibilities.
2. Show that the statement is true for each individual case.

Example 1

Prove that all square numbers are either a multiple of 4 or 1 more than a multiple of 4.

Let $n$ be any integer. We consider the square $n^2$. There are two cases for $n$:

• If $n$ is even, write $n = 2k$ for some integer $k$. Then
  $n^2 = (2k)^2 = 4k^2$, which is clearly a multiple of $4$.
• If $n$ is odd, write $n = 2k + 1$ for some integer $k$. Then
  $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 4k(k + 1) + 1$.
  Since $4k(k+1)$ is a multiple of $4$, $n^2$ is one more than a multiple of $4$.

Thus every square number is either a multiple of $4$ or one more than a multiple of $4$.