Proof by exhaustion

In a nutshell

Proof by exhaustion is a way of proving a statement that involves either testing every possible option or testing individual cases.

Testing every possible option

The most basic form of proof by exhaustion is to go through every single number and prove that all of them fit the claim.

Example 1

Prove that the square of every prime number between $$10$$ and $$20$$ ends in either a $$1$$ or a $$9$$.

Proof by exhaustion is reasonable to use here because there are not many numbers to check. 

List all the primes between $$10$$ and $$20$$:

$$11,13,17,19$$​​

Square all of these primes:

​$$11^2=121\\13^2=169\\17^2=289\\19^2=361$$​​

Hence, the square of all primes between these two numbers ends in a one or nine - the statement is correct.

Splitting up into cases

Another way to use proof by exhaustion is to split up the statement into two or more cases and address each case individually. This is helpful when proving more general cases.

Example 2

Prove that the square of any number is always a multiple of $$3$$ or $$1$$ more than a multiple of $$3$$.

Because the claim mentions multiples of $$3$$, split the cases into whether or not the number is a multiple of $$3$$.

A number can either be a multiple of $$3$$, $$1$$ more than a multiple of $$3$$ or $$2$$ more than a multiple of $$3$$.

Write these algebraically:

$$3n,3n+1,3n+2$$​​

Work with each case separately.

Case 1: $$3n$$

​$$(3n)^2=9n^2=3(3n^2)$$​​

So, this is a multiple of $$3$$.

Case 2: $$3n+1$$

$$(3n+1)^2=9n^2+6n+1=3(3n^2+2n)+1$$​​

So, this is $$1$$ more than a multiple of $$3$$.

Case 3: $$3n+2$$​

$$(3n+2)^2=9n^2+12n+4=3(3n^2+4n+1)+1$$​​

So, this is also $$1$$ more than a multiple of $$3$$.

Therefore, in every case, the square of a number is either a multiple of, or one more than a multiple of $$3$$. - the statement is correct.

​​​

​​