A1PureCore

Proof by Exhaustion

Proof by exhaustion breaks a statement into every possible case and checks each one. Used carelessly it looks like “testing examples” — used correctly, the cases are complete and finite, so checking them all is a genuine proof.

25 min Video by TLMaths Proof

The big picture

Exhaustion is the method students most often misunderstand, because on the surface it resembles the thing we just banned — trying examples. The difference is completeness. Testing n=1,2,3n = 1, 2, 3 leaves infinitely many untested. But if you can split every possibility into a finite\textbf{finite} number of cases that together miss nothing, then checking each case really does settle the whole claim. The insight that unlocks it: infinitely many integers can be sorted into just a few boxes — even or odd, or “remainder 0, 1 or 2 on division by 3”.

A-Level Maths A1-04: Introducing Proof by ExhaustionCurated by Kepler, not produced by us. Watch it, then work through the notes below.
Open on YouTube

What you'll be able to do

  • Recognise when a statement can be split into a finite, complete set of cases
  • Group infinitely many integers into a few classes (parity or remainders)
  • Write each case as a self-contained mini-proof and combine them
  • Judge when exhaustion is appropriate — and when it cannot work
1

Cases that leave nothing out

The engine of exhaustion is a complete\textbf{complete} set of cases: a way of dividing every possibility so that each one falls into exactly one case and none is missed. Prove the statement in every case and you have proved it in general — because there is nothing outside your cases.

The word “complete” is doing all the work. “The number is 1, 2 or 3” is only a valid exhaustion if those really are the only options. If a fourth possibility exists, checking the first three proves nothing.

Why this works

This is the one situation where checking cases is a valid proof — not because you checked many, but because you checked all\textbf{all} of them. Quantity is irrelevant; completeness is everything.

2

When the cases are already finite

Sometimes a statement only concerns a handful of values, and you can simply run through them. This is exhaustion at its most direct — but you must be systematic and visibly cover every option.

Example 1Prove that no square number ends in the digit 2, 3, 7 or 8.
1A number’s last digit is determined entirely by the last digit of the number being squared, so there are only 10 cases: last digit 0,1,2,…,90,1,2,\ldots,9.
2Squaring each and reading off the final digit: 0→0,  1→1,  2→4,  3→9,  4→6,  5→5,  6→6,  7→9,  8→4,  9→10\to0,\;1\to1,\;2\to4,\;3\to9,\;4\to6,\;5\to5,\;6\to6,\;7\to9,\;8\to4,\;9\to1.
3The possible final digits of a square are therefore only 0,1,4,5,6,90,1,4,5,6,9.
4None of these is 2,3,72,3,7 or 88, and the ten cases cover every integer.
Answer
A square can only end in 0,1,4,5,60,1,4,5,6 or 99, so never in 2,3,72,3,7 or 88. ■\blacksquare

Tip — When you reduce an “all integers” claim to “all possible last digits”, say so explicitly — that sentence is what turns 10 checks into a complete proof.

3

Turning infinitely many numbers into a few cases

The powerful version of exhaustion handles statements about all integers by sorting them into classes. Every integer is either even or odd — two classes, no exceptions. Every integer leaves a remainder of 0, 1 or 2 when divided by 3 — three classes. Prove the statement for each class and every integer is covered.

n=2k   or   n=2k+1(k∈Z)n = 2k \;\text{ or }\; n = 2k+1 \qquad (k \in \mathbb{Z})
Two complete cases that between them describe every integer.
Example 1Prove that n2+nn^2 + n is even for every integer nn.
1Split into the two complete cases: nn even or nn odd.
2Case 1 — n=2kn = 2k: n2+n=4k2+2k=2(2k2+k)n^2 + n = 4k^2 + 2k = 2(2k^2 + k), which is even.
3Case 2 — n=2k+1n = 2k+1: n2+n=(4k2+4k+1)+(2k+1)=4k2+6k+2=2(2k2+3k+1)n^2 + n = (4k^2 + 4k + 1) + (2k + 1) = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1), which is even.
4Both cases give an even result, and every integer is in one of them.
Answer
n2+nn^2 + n is even whether nn is even or odd, hence for all integers nn. ■\blacksquare
Example 2Prove that the square of any integer is either a multiple of 4 or one more than a multiple of 4.
1Every integer is even or odd — two complete cases.
2If n=2kn = 2k: n2=4k2n^2 = 4k^2, a multiple of 4.
3If n=2k+1n = 2k+1: n2=4k2+4k+1=4(k2+k)+1n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1, one more than a multiple of 4.
4These two cases exhaust every integer.
Answer
n2n^2 is of the form 4m4m or 4m+14m+1 for every integer nn. ■\blacksquare
Why this works

Notice why this beats testing: the two lines “n=2kn=2k” and “n=2k+1n=2k+1” between them are\textbf{are} every integer, so proving both is proving all infinitely many at once.

4

When exhaustion won’t work

Exhaustion needs a finite number of cases. You cannot exhaust a statement about all real numbers by cases, nor prove something for “all primes” by listing them, because those sets never end. If your cases are infinite, you need deduction or contradiction instead.

The honest test: before you start, can you name every case and be sure none is missing? If yes, exhaustion is valid. If the list would run forever, choose another method.

Think like an examiner

  • State clearly why your cases are complete\textbf{complete} — e.g. “every integer is even or odd”. Without that line, an examiner cannot tell exhaustion from example-testing.
  • Each case must be a proper mini-proof with its own algebra, not just a number that happens to work.
  • Finish with a combining statement: “in both cases… and these cases cover every integer, so…”. That sentence earns the final mark.
  • Exhaustion questions usually cap at a small number of cases (2 or 3). If your split produces many cases, you have probably chosen the wrong classification.

Common misconceptions

Checking n=1,2,3,4,5n = 1, 2, 3, 4, 5 and calling it proof by exhaustion.
Those are examples, not exhaustive cases — they miss every other integer. Cases must together cover all possibilities.
Splitting into cases that overlap or leave gaps.
Cases must be mutually exclusive and complete: each possibility in exactly one case, none missing.
Proving only the “interesting” case and assuming the others behave the same.
Every case needs its own argument — the whole point is that you have verified them all.
Using exhaustion on “all real xx” or “all primes”.
Those sets are infinite, so no finite list of cases can cover them. Use deduction or contradiction instead.

Complete case-splits

n=2k or 2k+1n = 2k \text{ or } 2k+1
Every integer: even or odd.
n=3k,  3k+1 or 3k+2n = 3k,\; 3k+1 \text{ or } 3k+2
Every integer by remainder mod 3.
n2≡0 or 1(mod4)n^2 \equiv 0 \text{ or } 1 \pmod 4
A proven consequence.

Stretch yourself

Prove by exhaustion that for every integer nn, the number n2n^2 is either a multiple of 3 or one more than a multiple of 3 — it is never two more than a multiple of 3.

Hint — Split every integer into three cases: n=3kn = 3k, n=3k+1n = 3k+1, n=3k+2n = 3k+2. Square each and simplify to reveal a multiple of 3, plus a remainder.

Reveal solution
SolutionEvery integer is 3k3k, 3k+13k+1 or 3k+23k+2. Then: (3k)2=9k2=3(3k2)(3k)^2 = 9k^2 = 3(3k^2), a multiple of 3; (3k+1)2=9k2+6k+1=3(3k2+2k)+1(3k+1)^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1, one more than a multiple of 3; (3k+2)2=9k2+12k+4=3(3k2+4k+1)+1(3k+2)^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1, again one more than a multiple of 3. All three cases give remainder 0 or 1, and they cover every integer, so n2n^2 is never two more than a multiple of 3. ■\blacksquare

Questions students ask

How is proof by exhaustion different from just testing examples?
Testing examples checks some cases and leaves the rest unknown. Exhaustion checks a complete, finite set of cases that between them cover every possibility — so nothing is left untested. Completeness, not quantity, is what makes it a proof.
How can I check infinitely many integers with only two or three cases?
By sorting them into classes. Every integer is even or odd (two classes) or has remainder 0, 1 or 2 on division by 3 (three classes). Proving the statement for each class proves it for every integer in that class at once.
When should I avoid exhaustion?
When the cases would be infinite — for example statements about all real numbers or all primes. If you cannot list every case and be sure none is missing, use deduction or contradiction instead.
How many cases is “too many”?
There is no hard limit, but A-Level questions are designed around a small number (usually two or three). If your split balloons, you have probably chosen the wrong way to classify — look for a parity or remainder split.

Key takeaways

  • Exhaustion proves a statement by checking a complete, finite set of cases.
  • It is valid because the cases cover every possibility — not because there are many of them.
  • Sort infinitely many integers into classes: even/odd, or remainders mod kk.
  • Write each case as its own mini-proof, then combine with a completeness statement.
  • Never use exhaustion where the cases are infinite (all reals, all primes).

How this fits the course

Test yourself

Answer a few questions, then review anything you missed.

Prefer paper? Open the written self-check

Answer each question before opening its answer. This self-check does not record a quiz score.

  1. Proof by exhaustion is valid because:

    • the cases together cover every possibility
    • a large number of cases are checked
    • the first few cases all work
    • it uses algebra
    Show answer and explanation

    Answer: the cases together cover every possibility

    Completeness is the key: the cases must leave nothing out.

  2. Which is a complete case-split for every integer nn?

    • n=2kn = 2k or n=2k+1n = 2k+1
    • n=2kn = 2k or n=2k+2n = 2k+2
    • n=1,2,3n = 1, 2, 3
    • n=3kn = 3k or n=3k+1n = 3k+1
    Show answer and explanation

    Answer: n=2kn = 2k or n=2k+1n = 2k+1

    Even or odd covers every integer exactly once. The mod-3 option is missing the 3k+23k+2 case.

  3. The possible final digits of a square number are:

    • 0,1,4,5,6,90,1,4,5,6,9
    • 0,2,4,6,80,2,4,6,8
    • any digit
    • 1,4,91,4,9
    Show answer and explanation

    Answer: 0,1,4,5,6,90,1,4,5,6,9

    Squaring each last digit 00–99 produces only these six final digits.

  4. Why can’t exhaustion prove a statement about all real numbers?

    • There are infinitely many cases that cannot be listed
    • Real numbers are too large
    • Exhaustion only works for even numbers
    • It can, with enough cases
    Show answer and explanation

    Answer: There are infinitely many cases that cannot be listed

    Exhaustion needs a finite, complete list of cases; the reals cannot be split that way.

  5. When nn is odd, n2+nn^2 + n equals:

    • 2(2k2+3k+1)2(2k^2 + 3k + 1)
    • 2(2k2+k)2(2k^2 + k)
    • 4k2+14k^2 + 1
    • 2k+12k+1
    Show answer and explanation

    Answer: 2(2k2+3k+1)2(2k^2 + 3k + 1)

    With n=2k+1n = 2k+1: (4k2+4k+1)+(2k+1)=4k2+6k+2=2(2k2+3k+1)(4k^2+4k+1)+(2k+1) = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1), which is even.

  6. A valid exhaustion proof for “all integers” must, above all, ensure the cases are:

    • complete and non-overlapping
    • as numerous as possible
    • all even
    • chosen at random
    Show answer and explanation

    Answer: complete and non-overlapping

    Each possibility must land in exactly one case, with none missing.

Next step

Keep practising

Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.

Browse practice topics

Related lessons

All 6 lessons

Put the methods into practice: see how A-Level maths duels work. An account is required to play; the overview and sample are public.