A3PureCore

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, 3$ leaves infinitely many untested. But if you can split every possibility into a $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 ExhaustionWatch the walkthrough, 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

Cases that leave nothing out

The engine of exhaustion is a $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$ of them. Quantity is irrelevant; completeness is everything.

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.

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, \dots, 9

2Squaring each and reading off the final digit:

0 \to 0, 1 \to 1, 2 \to 4, 3 \to 9, 4 \to 6, 5 \to 5, 6 \to 6, 7 \to 9, 8 \to 4, 9 \to 1

3The possible final digits of a square are therefore only

0, 1, 4, 5, 6, 9

4None of these is

2, 3, 7

8

, and the ten cases cover every integer.

AnswerA square can only end in

0, 1, 4, 5, 6

9

, so never in

2, 3, 7

8

■

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.

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 = 2 k or n = 2 k + 1 (k \in Z)

Two complete cases that between them describe every integer.

1Split into the two complete cases:

n

even or

n

odd.

2Case 1 —

n = 2 k

n^{2} + n = 4 k^{2} + 2 k = 2 (2 k^{2} + k)

, which is even.

3Case 2 —

n = 2 k + 1

n^{2} + n = (4 k^{2} + 4 k + 1) + (2 k + 1) = 4 k^{2} + 6 k + 2 = 2 (2 k^{2} + 3 k + 1)

, which is even.

4Both cases give an even result, and every integer is in one of them.

Answer

n^{2} + n

is even whether

n

is even or odd, hence for all integers

n

■

Why this works

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

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$ — 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, 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

x

” 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 = 2 k or 2 k + 1

Every integer: even or odd.

n = 3 k, 3 k + 1 or 3 k + 2

Every integer by remainder mod 3.

n^{2} \equiv 0 or 1 (mod 4)

A proven consequence.

Stretch yourself

Prove by exhaustion that for every integer $n$ , the number $n^{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 = 3 k$ , $n = 3 k + 1$ , $n = 3 k + 2$ . Square each and simplify to reveal a multiple of 3, plus a remainder.

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 $k$ .
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

Build on

Disproof by Counter-Example

Leads to

Disproof by Counter-Example

Test yourself

Ready to lock in Proof by Exhaustion? Pick a mode and earn XP & Dobloons.