Proof by exhaustion proves a statement is true by checking every possible case individually. When the number of cases is small and finite — for instance, all possible remainders when dividing by 3, or the last digit of all one-digit squares — exhaustion is a clean and complete proof strategy.
How is proof by exhaustion different from other proofs?
At GCSE you meet three types of proof:
| Proof type | Method | When to use |
|---|---|---|
| Algebraic proof | Use general expressions (e.g. 2n for even) to show a result holds for all values | When the statement is about all integers or all members of an infinite set |
| Counterexample | Find one value that breaks the statement | When disproving a claimed result |
| Exhaustion | Check every case in a finite, complete list | When there are a small, enumerable number of possibilities |
Proof by exhaustion is only valid when the cases are genuinely exhaustive — you must cover every possibility with no gaps.
When does exhaustion apply?
Exhaustion is suitable when the number of cases is small and clearly defined. Common contexts in GCSE:
- Last digits of powers (the last digit of n² only depends on the last digit of n, so there are exactly 10 cases: 0 through 9)
- Remainders modulo a small number (remainders when dividing by 3 are 0, 1, or 2 — just three cases)
- Parity combinations (n is odd or even — two cases)
- Days of the week, months of the year, or small finite sets given in the problem
If the number of cases is too large or infinite, exhaustion is impractical and you need algebraic proof instead.
Worked example 1: last digits of squares
Prove that no perfect square ends in the digit 2, 3, 7, or 8.
The last digit of n² depends only on the last digit of n. List all possible last digits (0 through 9) and square each:
| Last digit of n | n² | Last digit of n² |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 4 | 4 |
| 3 | 9 | 9 |
| 4 | 16 | 6 |
| 5 | 25 | 5 |
| 6 | 36 | 6 |
| 7 | 49 | 9 |
| 8 | 64 | 4 |
| 9 | 81 | 1 |
The last digits of squares are: {0, 1, 4, 5, 6, 9} only. The digits 2, 3, 7, and 8 never appear.
Since we have checked all 10 possible last digits and none gives a last digit of 2, 3, 7, or 8, the result is proved. □
Worked example 2: squares divided by 3
Prove that for any integer n, n² leaves a remainder of 0 or 1 when divided by 3.
Any integer leaves a remainder of 0, 1, or 2 when divided by 3. Those are the only three cases.
Case 1: n leaves remainder 0. Then n = 3k for some integer k. So n² = 9k² = 3(3k²), which is divisible by 3. Remainder 0.
Case 2: n leaves remainder 1. Then n = 3k + 1. So n² = 9k² + 6k + 1 = 3(3k² + 2k) + 1. Remainder 1.
Case 3: n leaves remainder 2. Then n = 3k + 2. So n² = 9k² + 12k + 4 = 9k² + 12k + 3 + 1 = 3(3k² + 4k + 1) + 1. Remainder 1.
All three cases have been covered. In every case, n² leaves remainder 0 or 1. □
Worked example 3: a simple parity argument
Prove that n² + n is always even for any integer n.
There are exactly two cases: n is even, or n is odd.
Case 1: n is even. Then n = 2k. So n² + n = 4k² + 2k = 2(2k² + k), which is even.
Case 2: n is odd. Then n = 2k + 1. So n² + n = (2k+1)² + (2k+1) = 4k² + 4k + 1 + 2k + 1 = 4k² + 6k + 2 = 2(2k² + 3k + 1), which is even.
Both cases give an even result. Since every integer is either even or odd, n² + n is always even. □
(Note: you could also argue that n² + n = n(n + 1), which is the product of two consecutive integers and therefore always even — but the exhaustion approach above is equally valid.)
How do you write up an exhaustion proof clearly?
- State the cases explicitly. Tell the reader what the finite list of cases is and why it is complete.
- Check each case. Show the algebra or arithmetic clearly for every case — do not skip any.
- Conclude. State that since all cases are covered and the result holds in each one, the proof is complete.
A missing case is a gap in the proof and loses marks. If the question says there are three possible remainders, you must address all three — not just the easy ones.
Frequently asked questions
Is proof by exhaustion less rigorous than algebraic proof?
No. When the cases truly are finite and your list is complete, exhaustion is a perfectly valid mathematical proof. The risk is failing to cover all cases, or assuming a list is complete when it isn't. State clearly why your list exhausts all possibilities.
When should I choose exhaustion over algebraic proof?
Choose exhaustion when the number of cases is small (typically fewer than ten) and each case is easy to check. For infinite sets — "prove this is true for all integers" — you cannot exhaust infinitely many cases and must use algebra. If both methods are valid, algebraic proof is usually more elegant, but exhaustion earns the same marks.
Do I need to write "Case 1, Case 2, ..." formally?
GCSE mark schemes do not require a rigid layout, but labelling your cases clearly ("When n is even..." / "When n is odd...") helps the examiner follow your argument and gives you a checklist to ensure you haven't skipped one.
Can exhaustion disprove a statement?
Not directly — to disprove a statement you use a single counterexample. Exhaustion proves statements true by showing all cases work. If any single case fails, the statement is false — but in that situation, you would present just that one failing case as the counterexample rather than listing all the others.
Work through proof questions Socratically with Professor Pi — add the connector at aitutors.me.