4.3 Proof by cases

Depending on the mathematical objects involved in a statement, it may be possible to consider mutually-exclusive cases and prove each case separately.

To illustrate this idea, we revisit the result from Exercise 4.12, where we proved that if $n$ is an integer then $n^{2}+n$ is even.

Example 4.16.

We shall prove that if $n$ is any integer then $n^{2}+n$ is even using a proof by cases.

Since $n$ is an integer, we know that it must even or odd, but not both. We can consider these two cases separately.

Case 1: Suppose $n$ is even, so we know that $n=2k$ for some integer $k$ . Then $n+1=2k+1$ and we see that

	$\displaystyle n^{2}+n$	$\displaystyle=n(n+1)$
		$\displaystyle=(2k)(2k+1)$
		$\displaystyle=2\times k(2k+1)$

and so $n^{2}+n$ is even (since it is $2$ times an integer [why?]).

Case 2: Now suppose $n$ is odd, so can write $n=2k+1$ for some integer $k$ . (Note that we are reusing $k$ since we are done with the previous case.) Then $n+1=2k+2$ and we see that

	$\displaystyle n^{2}+n$	$\displaystyle=n(n+1)$
		$\displaystyle=(2k+1)(2k+2)$
		$\displaystyle=2\times k(2k+1).$

Hence $n^{2}+n$ is even.

The proof is complete.

When using proof by cases we split a difficult general proof into many sub-proofs. Each sub-proof has an extra specific hypothesis. In the above example that was ‘ $n$ is odd’ or ‘ $n$ is even’. The extra hypothesis gives more information, and helps make the sub-proof easier.

Mathematicians are sometimes dissatisfied with proofs by cases. While they do establish that a statement is true, they often do not really explain why it is true. Recall from Section 1.4 that mathematicians sometimes prefer proofs which explain over proofs which just establish truth.

4.3.1 Proof by exhaustion

A statement may assert something about a finite number of objects. If so then it may be possible to verify the statement for each object separately.

Example 4.17.

We prove that for $x=2,3,4$ , the expression $x^{2}-3$ is greater than $0$ and less than $14$ .

Because this is a statement about a finite number of values, we can check each separately:

•

if $x=2$ then $x^{2}-3=4-3=1$ ;
•

if $x=3$ then $x^{2}-3=9-3=6$ ; and
•

if $x=4$ then $x^{2}-3=16-3=13$ .

Hence $x^{2}-3$ is between 0 and 14 for $x=2,3,4$ . The proof is complete.

Exercise 4.18.

Prove that there are exactly two prime numbers greater than 20 and less than 30.

Solution.
- –
  
  $21=3\times 7$ is not prime.
- –
  
  $22=2\times 11$ is not prime.
- –
  
  $23$ is prime.
- –
  
  $24=2\times 12$ is not prime.
- –
  
  $25=5\times 5$ is not prime.
- –
  
  $26=2\times 13$ is not prime.
- –
  
  $27=3\times 9$ is not prime.
- –
  
  $28=2\times 14$ is not prime.
- –
  
  $29$ is prime.
So there are exactly two prime numbers greater than $20$ and less than $30$ . The proof is complete.
This is a pretty mindless way of proving this result. You could reduce the number of cases you have to consider by first noting that any even number greater than $2$ cannot be prime, and so you only really have to check the odd numbers between $20$ and $30$ .

Example 4.19.

The four colour theorem is a famous example of a result involving a proof by exhaustion. In 1976, a computer algorithm was used to check 1834 cases in order to verify the claim of the theorem.