Proof by Exhaustion

Proving statements by checking every possible case

SPEC 1.1 • PROOF

What is Proof by Exhaustion?

Definition

Proof by exhaustion is a method where we prove a statement by checking ALL possible cases. If the statement holds true for every case, then it must be true in general.

This method works when we can split all possibilities into a finite number of cases that cover every scenario.

When to Use

When there are only a finite number of cases to check

When cases can be categorised completely (e.g., odd/even)

When a direct algebraic proof is difficult or impossible

Key Idea

The cases must be exhaustive (cover everything) and mutually exclusive (no overlaps).

Identifying Cases

The key to proof by exhaustion is choosing the right way to split into cases:

Strategy

1. Identify the variable - What are we proving something about?

2. Find natural divisions - How can we split all possibilities?

3. Check completeness - Do our cases cover everything?

4. Prove each case - Show the statement holds for each

Important

You must explicitly state all your cases and show that they cover ALL possibilities. Missing a case invalidates the entire proof!

Common Case Divisions

Division TypeCasesUse When

Odd / Even

n = 2 k

or

n = 2 k + 1

Proving divisibility by 2

Remainder when dividing by 3

n = 3 k

,

3 k + 1

, or

3 k + 2

Proving divisibility by 3

Remainder when dividing by 4

n = 4 k

,

4 k + 1

,

4 k + 2

,

4 k + 3

Proving divisibility by 4

Finite SetCheck each value individuallySmall number of specific values

SignPositive, negative, zeroInequalities, absolute values

Most Common

The odd/even split is the most frequently used in A-Level exams. Every integer is either odd OR even - there's no third option!

Worked Example01

Prove by exhaustion that $n^{2} + n$ is even for all integers $n$ .

We consider two cases: $n$ is even, or $n$ is odd.

Case 1: n is even

Let

n = 2 k

for some integer

k

.

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

This is a multiple of 2, so it is even. ✓

Case 2: n is odd

Let

n = 2 k + 1

for some integer

k

.

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

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

This is a multiple of 2, so it is even. ✓

Conclusion: Since all integers are either even or odd, and

n^{2} + n

is even in both cases,

n^{2} + n

is even for all integers

n

.

Worked Example02

Prove by exhaustion that $(n + 1)^{3} - n^{3}$ is odd for all positive integers $n$ .

We consider two cases: $n$ is even, or $n$ is odd.

Case 1: n is even

Let

n = 2 k

, so

n + 1 = 2 k + 1

(odd).

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

= 8 k^{3} + 12 k^{2} + 6 k + 1 - 8 k^{3} = 12 k^{2} + 6 k + 1

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

This is of the form

2 m + 1

, so it is odd. ✓

Case 2: n is odd

Let

n = 2 k + 1

, so

n + 1 = 2 k + 2 = 2 (k + 1)

(even).

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

= 8 (k + 1)^{3} - (8 k^{3} + 12 k^{2} + 6 k + 1)

= 8 k^{3} + 24 k^{2} + 24 k + 8 - 8 k^{3} - 12 k^{2} - 6 k - 1

= 12 k^{2} + 18 k + 7 = 2 (6 k^{2} + 9 k + 3) + 1

This is of the form

2 m + 1

, so it is odd. ✓

Conclusion: In both cases,

(n + 1)^{3} - n^{3}

is odd. Therefore it is odd for all positive integers

n

.

Worked Example03

Prove that $n^{3} - n$ is divisible by 6 for all positive integers $n$ .

Method: Factorise first, then use case analysis.

1

n^{3} - n = n (n^{2} - 1) = n (n - 1) (n + 1) = (n - 1) n (n + 1)

2

This is the product of three consecutive integers.

Divisibility by 2

Of any two consecutive integers, one must be even.

So

(n - 1) n (n + 1)

contains at least one factor of 2. ✓

Divisibility by 3

Of any three consecutive integers, exactly one is divisible by 3.

So

(n - 1) n (n + 1)

contains exactly one factor of 3. ✓

Conclusion: Since

n^{3} - n

is divisible by both 2 and 3, and 2 and 3 share no common factors, it is divisible by

2 \times 3 = 6

.

Worked Example04

Verify that $n^{2} - n + 11$ is prime for $n = 1, 2, 3, 4, 5$ .

We check each value of $n$ individually:

Conclusion: By exhaustion,

n^{2} - n + 11

is prime for all

n \in {1, 2, 3, 4, 5}

.

Note: This does NOT prove it's prime for all

n

! In fact, when

n = 11

:

121 - 11 + 11 = 121 = 1 1^{2}

, which is not prime.

Worked Example05

Show by exhaustion that $6 n - 1$ is prime for $n = 1, 2, 3, 4, 5$ .

We check each value of $n$ individually:

Conclusion: By exhaustion,

6 n - 1

is prime for all

n \in {1, 2, 3, 4, 5}

.

Check: When

n = 6

:

6 (6) - 1 = 35 = 5 \times 7

, which is NOT prime. This shows the pattern doesn't continue forever!

Exhaustion vs Deduction

Proof by ExhaustionProof by Deduction

Check ALL cases separatelyOne general algebraic argument

Works for finite/categorised casesWorks for infinite sets directly

Can be long if many casesUsually more elegant

Useful when algebra is messyRequires algebraic manipulation

Exam Tip

If a question says "prove by exhaustion", you MUST use cases. Don't use a single algebraic argument - even if it would work!

Worked Example06

Prove that all prime numbers greater than 2 are odd.

We consider the two cases for any integer greater than 2:

Case 1: The number is even

Let the number be

n = 2 k

where

k > 1

.

Then

n = 2 \times k

, so

n

has 2 as a factor.

Since

n > 2

, we have

k > 1

, so

n

is divisible by 2 and is NOT prime. ✗

Case 2: The number is odd

Odd numbers greater than 2 can be prime (e.g., 3, 5, 7, 11, ...).

This case does allow for prime numbers. ✓

Conclusion: Since even numbers greater than 2 are never prime, all primes greater than 2 must be odd.

Limitations of Exhaustion

Warning

Proof by exhaustion can only prove statements about finite sets or sets that can be completely categorised.

You CANNOT use exhaustion for:

Infinitely many uncategorised cases (e.g., "prove for all real numbers")

Statements where cases cannot be completely listed

General patterns that extend indefinitely

Remember

Checking a few examples is NOT exhaustion. You must check ALL cases, or prove something about ALL possible categories.

Practice

Question 1: Prove by exhaustion that

(2 n - 1)^{2}

is odd for all integers

n

.

Note:

2 n - 1

is always odd regardless of whether

n

is odd or even!

We can show this directly:

2 n - 1 = 2 n - 2 + 1 = 2 (n - 1) + 1

This is of the form

2 k + 1

, so

2 n - 1

is always odd.

Now:

(2 n - 1)^{2} = (2 n - 1) (2 n - 1) = odd \times odd = odd

✓

Alternatively by cases:

All integers

(2 n - 1)^{2} = 4 n^{2} - 4 n + 1 = 2 (2 n^{2} - 2 n) + 1

This is always of the form

2 m + 1

, so always odd. ✓

Practice

Question 2: Prove by exhaustion that

n^{3} + n

is even for all positive integers

n

.

We consider two cases:

Case 1: n is even

Let

n = 2 k

for some integer

k

.

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

This is a multiple of 2, so even. ✓

Case 2: n is odd

Let

n = 2 k + 1

for some integer

k

.

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

= 8 k^{3} + 12 k^{2} + 6 k + 1 + 2 k + 1

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

This is a multiple of 2, so even. ✓

Conclusion: In both cases,

n^{3} + n

is even.

Practice

Question 3: Investigate whether

2^{n} > n^{2}

is true for

n = 1, 2, 3, 4, 5

.

Check each value:

Conclusion: The statement

2^{n} > n^{2}

is NOT true for all

n \in {1, 2, 3, 4, 5}

. It is false when

n = 2, 3, 4

.

Summary

Key Points

ConceptDetails

Proof by ExhaustionProve by checking ALL possible cases

Case DivisionSplit into exhaustive, mutually exclusive categories

Common SplitsOdd/even, remainders when dividing by 3/4, finite sets, sign

ConclusionMust state that all cases have been covered

Exam Skills

Always state your cases clearly at the start

Verify each case completely with full working

Write a clear conclusion linking back to all cases

Remember: finite sets only prove for those specific values!