Proof by Exhaustion

Proof by exhaustion is a method of proof in which you verify a statement by checking every possible case. Once you have confirmed that the statement holds in every case, the proof is complete. This technique is only practical when the number of cases is finite and manageable.

In the AQA A-Level Mathematics specification (7357), proof by exhaustion is listed as one of the four types of proof that students must understand and be able to apply. It is a legitimate and powerful method when used appropriately.

---

When to Use Proof by Exhaustion

Proof by exhaustion is appropriate when:

• The statement applies to a finite, small set of cases.
• It is not immediately clear how to construct a deductive proof.
• The problem explicitly restricts the domain to a small set (e.g., "for n = 1, 2, 3, 4, 5").

It is not appropriate when:

• The domain is infinite (e.g., "for all positive integers").
• The number of cases is impractically large.

Exam Tip: If the question says "for 1 ≤ n ≤ 5" or "for all single-digit primes," exhaustion is usually expected. If the domain is infinite, you need deduction or contradiction instead.

---

The Structure of a Proof by Exhaustion

1. Identify all possible cases that need to be checked.
2. Check each case individually, showing the required computation or reasoning.
3. Conclude by stating that the result has been verified for all cases.

---

Worked Examples

Example 1: Prove that n² + n + 11 is prime for all positive integers n where 1 ≤ n ≤ 4.

We check each value of n:

n	n² + n + 11	Prime?
1	1 + 1 + 11 = 13	Yes (prime)
2	4 + 2 + 11 = 17	Yes (prime)
3	9 + 3 + 11 = 23	Yes (prime)
4	16 + 4 + 11 = 31	Yes (prime)

All four cases have been checked, and in each case n² + n + 11 is prime.

Therefore, n² + n + 11 is prime for all positive integers n where 1 ≤ n ≤ 4. ∎

Note: This does not prove the result for all n. In fact, when n = 10, we get 10² + 10 + 11 = 121 = 11², which is not prime. Exhaustion only covers the stated cases.

---

Example 2: Prove that (n + 1)³ > 3n for all positive integers n where 1 ≤ n ≤ 5.

n	(n + 1)³	3n	(n + 1)³ > 3n?
1	8	3	Yes
2	27	9	Yes
3	64	27	Yes
4	125	81	Yes
5	216	243	No!

Wait — when n = 5, (n + 1)³ = 216 and 3⁵ = 243, so (n + 1)³ < 3n.

This means the statement is false for 1 ≤ n ≤ 5. The exhaustive check has found a counterexample at n = 5.

Exam Tip: If the exhaustive check reveals a case where the statement fails, the proof fails. Report this honestly. The question may have been designed to test whether you can identify that a statement is false.

---

Example 3: Prove that for any prime number p where 2 ≤ p ≤ 19, the number p² + 2 is not divisible by 3.

The primes in the range 2 ≤ p ≤ 19 are: 2, 3, 5, 7, 11, 13, 17, 19.

p	p² + 2	Divisible by 3?
2	6	Yes!

At p = 2, we find p² + 2 = 6, which is divisible by 3. Also, at p = 3, we get p² + 2 = 11, which is not divisible by 3.

Actually, let us reconsider this example. The statement is false (p = 2 gives a counterexample). This illustrates the importance of careful checking.

Let us instead prove a true statement.

Example 3 (revised): Prove that for every integer n with 1 ≤ n ≤ 6, the value n³ + 5n is divisible by 6.

n	n³ + 5n	÷ 6	Divisible?
1	1 + 5 = 6	1	Yes
2	8 + 10 = 18	3	Yes
3	27 + 15 = 42	7	Yes
4	64 + 20 = 84	14	Yes
5	125 + 25 = 150	25	Yes
6	216 + 30 = 246	41	Yes

All six cases have been checked. In each case, n³ + 5n is divisible by 6.

Therefore, n³ + 5n is divisible by 6 for all integers n where 1 ≤ n ≤ 6. ∎

---

Example 4: Systematic Case Analysis — Parity

Some proofs by exhaustion split into a small number of general cases rather than individual values. This is particularly common when you split integers into even and odd.

Prove that n² − n is even for all integers n.

We consider two cases: n is even, and n is odd.

Case 1: n is even. Let n = 2k.

n² − n = (2k)² − 2k = 4k² − 2k = 2(2k² − k)

This is even.

Case 2: n is odd. Let n = 2k + 1.

n² − n = (2k + 1)² − (2k + 1) = 4k² + 4k + 1 − 2k − 1 = 4k² + 2k = 2(2k² + k)

This is even.

In both cases, n² − n is even. Since every integer is either even or odd, this covers all integers.

Therefore, n² − n is even for all integers n. ∎

Note: This is sometimes called proof by cases and can be considered a form of exhaustion over a finite partition of the domain.

---

Example 5: Prove that for all integers n, n³ mod 9 is one of 0, 1, or 8.

Every integer n is congruent to one of 0, 1, 2, 3, 4, 5, 6, 7, or 8 modulo 9. We check n³ mod 9 for each:

n mod 9	n³ mod 9
0	0
1	1
2	8 (since 8 = 512/64... actually 2³ = 8)
3	27 mod 9 = 0
4	64 mod 9 = 1
5	125 mod 9 = 8
6	216 mod 9 = 0
7	343 mod 9 = 1
8	512 mod 9 = 8

In every case, n³ mod 9 ∈ {0, 1, 8}.

Therefore, for all integers n, n³ mod 9 is 0, 1, or 8. ∎

---

Exhaustion vs Deduction

Feature	Proof by Exhaustion	Proof by Deduction
Domain	Finite, small	Can be infinite
Method	Check every case	Logical argument
Generality	Covers only stated cases	Covers all cases
Effort	Increases with number of cases	Independent of case count
When to use	Small finite sets, or case-splitting	General statements

---

Organising Your Work

When presenting a proof by exhaustion in an exam:

1. List the cases clearly — use a table if possible.
2. Show the calculation for each case — do not skip steps.
3. State whether the condition holds in each case.
4. Conclude with a clear statement confirming that all cases have been checked and the result holds (or state if a counterexample was found).

---

Summary

• Proof by exhaustion works by checking every possible case.
• It is appropriate only when the number of cases is finite and manageable.
• Organise your work in a table for clarity.
• A proof by exhaustion over a finite domain is complete and valid — but it says nothing about cases outside the stated domain.
• Case splitting (e.g., even/odd) is a form of exhaustion when the cases partition the entire domain.
• Always end with a concluding sentence stating what has been proved.

Exam Tip: In AQA exams, proof by exhaustion questions typically specify a small domain such as "for 1 ≤ n ≤ 5" or "for all prime numbers less than 20." Present your answer in a table, show all calculations clearly, and write a concluding statement. If the question does not restrict the domain to a finite set, exhaustion is almost certainly not the intended method.

A-Level Deep Dive: Proof by Exhaustion

Spec mapping

AQA 7357 specification, Paper 1 — Pure Mathematics, Section A: Proof. The specification requires students to "understand and use the structure of mathematical proof, proceeding from given assumptions through a series of logical steps to a conclusion; use methods of proof, including proof by deduction, proof by exhaustion, [and] disproof by counter-example." Proof by exhaustion sits inside this proof toolkit and is examined principally on Paper 1, but the style of reasoning it embeds — splitting a problem into cases and arguing each — recurs across modular arithmetic problems in Pure Section A, piecewise integration in Section L (Integration), case-based inequality work in Section B (Algebra and functions) and boundary-case mechanics arguments in Paper 3 Section P (Forces and Newton's laws). The AQA formula booklet does not list any proof templates — the structure must be internalised.

---

Worked example with full mark scheme

Question (8 marks):

(a) Prove by exhaustion that for every integer $n$n, the expression $n^2 + n$n2+n is even. (5)

(b) Hence, or otherwise, deduce that for every integer $n$n, the expression $n^3 - n$n3−n is divisible by 2. (3)

Solution with mark scheme:

(a) Step 1 — set up the case split.

Every integer $n$n is either even or odd. These two cases are exhaustive (they cover all integers) and mutually exclusive (no integer is both). It therefore suffices to prove the statement for each case separately.

M1 — explicit statement that the cases "n even" and "n odd" exhaust the integers. The wording matters: examiners check that the candidate has justified exhaustiveness, not merely assumed it. Writing "let n be even or odd" without the partition argument loses the M1.

Step 2 — case 1, n even.

Suppose $n$n is even. Then $n = 2k$n=2k for some integer $k$k. Substituting:

$n^2 + n = (2k)^2 + 2k = 4k^2 + 2k = 2(2k^2 + k)$n2+n=(2k)2+2k=4k2+2k=2(2k2+k)

Since $2k^2 + k$2k2+k is an integer (sum and product of integers), $n^2 + n$n2+n is a multiple of 2 and therefore even.

M1 — correct algebraic substitution $n = 2k$n=2k and factorisation revealing the factor of 2.

A1 — explicit conclusion that case 1 yields an even result, with the integrality of the bracketed expression noted.

Step 3 — case 2, n odd.

Suppose $n$n is odd. Then $n = 2k + 1$n=2k+1 for some integer $k$k. Substituting:

$n^2 + n = (2k + 1)^2 + (2k + 1) = 4k^2 + 4k + 1 + 2k + 1 = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1)$n2+n=(2k+1)2+(2k+1)=4k2+4k+1+2k+1=4k2+6k+2=2(2k2+3k+1)

Since $2k^2 + 3k + 1$2k2+3k+1 is an integer, $n^2 + n$n2+n is again a multiple of 2 and therefore even.

M1 — correct algebraic substitution $n = 2k + 1$n=2k+1 and expansion through to a factor of 2.

Step 4 — concluding statement.

Both cases yield $n^2 + n$n2+n even, and the cases are exhaustive over the integers. Therefore $n^2 + n$n2+n is even for every integer $n$n, as required.

A1 — final concluding sentence linking the two cases back to the original claim. Many candidates prove both cases correctly but never write the joining sentence; the A1 is reserved for that closure.

(b) Step 1 — factorise.

$n^3 - n = n(n^2 - 1) = n(n - 1)(n + 1)$n3−n=n(n2−1)=n(n−1)(n+1).

M1 — correct factorisation. Recognising the difference of squares is the prompt.

Step 2 — connect to part (a).

Note that $n^3 - n = n(n + 1)(n - 1)$n3−n=n(n+1)(n−1). The product $n(n + 1)$n(n+1) equals $n^2 + n$n2+n, which by part (a) is even. Multiplying an even integer by any integer (here $n - 1$n−1) yields an even integer.

M1 — using the result of part (a) directly, honouring the "Hence" command.

A1 — concluding statement that $n^3 - n$n3−n is divisible by 2 for every integer $n$n.

Total: 8 marks (M5 A3, split as shown).

---

Specimen question modelled on the AQA 7357 Paper 1 format

Question (6 marks): Prove by exhaustion that for every positive integer $n$n with $1 \leq n \leq 5$1≤n≤5, the expression $n^3 + 2n$n3+2n is divisible by 3.

Mark scheme decomposition by AO:

• M1 (AO2.1) — recognising that exhaustion is appropriate because the domain $1 \leq n \leq 5$1≤n≤5 is finite and small (five cases), and stating an intention to evaluate each.
• M1 (AO1.1a) — correctly evaluating $n^3 + 2n$n3+2n for at least three of the five cases. Typically a tabulation: $n = 1$n=1 gives $3$3; $n = 2$n=2 gives $12$12; $n = 3$n=3 gives $33$33; $n = 4$n=4 gives $72$72; $n = 5$n=5 gives $135$135.
• A1 (AO1.1b) — all five values evaluated correctly and divisibility by 3 noted in each case ($3 = 3 \cdot 1$3=3⋅1; $12 = 3 \cdot 4$12=3⋅4; $33 = 3 \cdot 11$33=3⋅11; $72 = 3 \cdot 24$72=3⋅24; $135 = 3 \cdot 45$135=3⋅45).
• M1 (AO2.4) — presentation in a structured table or list, with the divisibility claim made explicit per row.
• A1 (AO2.5) — concluding statement: "Since each case yields a multiple of 3, the claim holds for every integer $n$n with $1 \leq n \leq 5$1≤n≤5, as required."
• A1 (AO2.2a) — explicit acknowledgement that the proof is only valid for the stated domain and says nothing about $n = 6$n=6 or beyond.

Total: 6 marks split AO1 = 2, AO2 = 4. Exhaustion questions are AO2-heavy because the technique is procedurally trivial — the marks reward the framing (justifying exhaustiveness, presenting cleanly, writing a concluding sentence, noting domain restriction) rather than the arithmetic.

---

Synoptic links

Connects to:

1. Proof by deduction (Pure Section A): deduction proves a general claim by algebraic argument from definitions; exhaustion proves it by checking every case. Many problems admit both methods — the part (a) above could be done by deduction (write $n^2 + n = n(n + 1)$n2+n=n(n+1) and observe consecutive integers contain an even number) more elegantly than by exhaustion. Choosing exhaustion when deduction is available is a strategic loss.

2. Case analysis in inequalities (Section B): solving $|x - 2| < |x + 1|$∣x−2∣<∣x+1∣ requires splitting into cases based on the sign of each modulus argument. The structural move — partition the domain, prove on each piece, recombine — is exactly the case-splitting move of exhaustion.

3. Modular arithmetic and the "p mod q" idiom: showing that $n^2 \equiv 0$n2≡0 or $1 \pmod 4$1(mod4) for every integer $n$n is a case-based proof over the residues modulo 4. Every integer is congruent to 0, 1, 2 or 3 mod 4, and these four cases exhaust the integers under the equivalence. The infinity of the integers collapses into a finite exhaustion via the equivalence relation.

4. Computer-assisted proofs (university): the four-colour theorem (every planar map is 4-colourable) was proved in 1976 by reducing the problem to a finite list of "unavoidable configurations" and checking each by computer — an exhaustion proof on a scale impossible by hand. The Kepler conjecture (densest sphere packing) was similarly resolved by Hales in 1998 via case-checking with linear programming. These are the canonical examples of exhaustion at industrial scale.

5. Piecewise functions (Section H): integrating a piecewise function over a domain crossing the breakpoints requires evaluating each piece separately and summing. The structural template — partition, evaluate, combine — is the exhaustion template applied to integration rather than divisibility.

---

Mark-scheme literacy

Exhaustion questions on 7357 split AO marks heavily toward AO2: