Proof by Exhaustion and Counter-example

Build a proof as a chain of logical steps, prove a statement by checking every case, and disprove a claim with one counter-example.

In the exam for Edexcel International AS Maths · 15 real past-paper questions below

Checking is not proving

Put $n = 0, 1, 2, 3, \dots$ into $n^{2} + n + 41$ . You get 41, 43, 47, 53, … All prime. Keep going up to $n = 39$ . Still prime every time. Is it always prime?

No. At $n = 40$ you get $1681 = 41 \times 41$ . Forty good examples, and the claim is still false.

Key idea

The mathematician Leonhard Euler wrote about this expression in 1772. It gives primes for $n = 0$ to $39$ , then breaks.

Rule

Examples never prove a statement that is about infinitely many numbers. But one example that fails is enough to show it is false.

A proof is a chain of reasoning that works for every case at once. It has three parts.

Steps

1
1. Start from what you are given: “Let $n$ be an odd integer…”
2. Reason one step at a time. Each line follows from the line before.
3. Conclude: say clearly that the statement is true.

Key idea

Checking a few numbers tests a claim. A proof covers every case. A counter-example kills a claim.

Disproof by counter-example

A counter-example is one case where the statement is false. To use it, you must do two things: show the calculation, and say why it breaks the claim.

Worked example

1
Show that this statement is false: “If $p$ is prime, then $2 p + 3$ is prime.”
2
$p = 2 : 2 (2) + 3 = 7$ — Prime. This value does not help, so try another.
3
$p = 3 : 2 (3) + 3 = 9$ — Next prime. Is 9 prime?
4
$9 = 3 \times 3$ — So 9 is not prime.
5
$p = 3$ — This is a counter-example, so the statement is false.

Statements about real numbers break the same way. Look for negatives, fractions or zero.

Worked example

1
Show that “if $x > y$ then $x^{2} > y^{2}$ ” is not true for all real numbers.
2
$x = 1, y = - 3$ — Try a negative $y$ . Here $1 > - 3$ .
3
$x^{2} = 1, y^{2} = 9$ — Square both.
4
$1 < 9$ — So $x > y$ but $x^{2} < y^{2}$ . The statement is false.

Common mistake

Writing only “ $2 (3) + 3 = 9$ , so false”. Mark schemes have refused the last mark for this. Add the reason: “9 = 3 × 3, which is not prime”.

Common mistake

Using 1 as a prime. 1 is not prime, so it cannot be a counter-example in a statement about primes.

Common mistake

Breaking “irrational × irrational is always irrational”? Give the answer as a rational number: $5 \times 20 = 100 = 10$ . Stopping at $100$ can lose the mark.

Key idea

One clear case, the calculation, and the words “which is not prime, so the statement is false”.

Proof by exhaustion

Sometimes there are only a few possible cases. Then you can prove a statement by checking every one. This is proof by exhaustion: you exhaust (use up) all the cases.

Worked example

1
$a$ , $b$ and $c$ are positive integers. $b = a + 3$ and $a + b + c = 12$ . Prove by exhaustion that $ab c$ is always even.
2
$c = 12 - a - (a + 3) = 9 - 2 a$ — Write $c$ in terms of $a$ .
3
$9 - 2 a > 0 \Rightarrow a < 4.5$ — $c$ must be positive. So $a = 1, 2, 3$ or $4$ : four cases only.
4
$a = 1 : 1 \times 4 \times 7 = 28$ — Case 1.
5
$a = 2 : 2 \times 5 \times 5 = 50$ — Case 2.
6
$a = 3 : 3 \times 6 \times 3 = 54$ — Case 3.
7
$a = 4 : 4 \times 7 \times 1 = 28$ — Case 4.
8
$28, 50, 54, 28 are all even$ — These are all the cases, so $ab c$ is always even.

A table is a tidy way to set this out. Marks come for one correct case, then two, then all cases with a conclusion.

Common mistake

Missing a case, or keeping one that is not allowed, like $a = 5$ which makes $c = - 1$ . Cross out any row that breaks the conditions.

Common mistake

Stopping at the numbers. Say what they show: “all are even, so $ab c$ is always even”.

Key idea

Exhaustion = list every allowed case, check each one, then say “these are all the cases, so the statement is true”.

Integers in algebra

You cannot check every whole number. Instead, use a letter that stands for any integer. Then one line of algebra covers them all.

Formula

even = 2 k odd = 2 k + 1 consecutive: n, n + 1

$k$ — any integer. An even number is 2 times something; an odd number is one more.
$n$ — any integer. The next integer is one more.

Two consecutive odd numbers: $2 k + 1$ and $2 k + 3$ .

Not a multiple of 3? It leaves remainder 1 or 2, so it is $3 k + 1$ or $3 k + 2$ .

Memory trick

Start with Let, end with So. “Let $n = 2 k + 1$ , where $k$ is an integer … So the statement is true.”

Worked example

1
Prove that the difference between the squares of two consecutive odd numbers is a multiple of 8.
2
$Let the numbers be 2 k + 1 and 2 k + 3$ — Where $k$ is an integer. Say what $k$ is.
3
$(2 k + 3)^{2} - (2 k + 1)^{2}$ — Write the difference.
4
$= (4 k^{2} + 12 k + 9) - (4 k^{2} + 4 k + 1)$ — Expand both brackets.
5
$= 8 k + 8 = 8 (k + 1)$ — Collect terms. Take out the factor 8.
6
$k + 1 is an integer$ — So $8 (k + 1)$ is a multiple of 8. The statement is true.

Common mistake

Using $n$ for the integer and again for the odd number, as in $n = 2 n + 1$ . Use a new letter, like $k$ . Mark schemes can withhold the final mark.

Common mistake

Writing an odd number as $4 k + 1$ . That misses 3, 7, 11, … Use $2 k + 1$ so every odd number is included.

Key idea

Write the number with a new letter, expand, take out the factor, and say what it shows.

Exhaustion with algebra

Every integer is even or odd. So “prove for all integers” can be split into two cases: $n = 2 k$ and $n = 2 k + 1$ . Prove both and you have covered every integer.

Worked example

1
Use algebra to prove by exhaustion that $n^{2} + 3 n + 6$ is even for every integer $n$ .
2
$n = 2 k : (2 k)^{2} + 3 (2 k) + 6 = 4 k^{2} + 6 k + 6$ — Case 1: $n$ even, $k$ an integer.
3
$= 2 (2 k^{2} + 3 k + 3)$ — Take out 2. This is even.
4
$n = 2 k + 1 : (2 k + 1)^{2} + 3 (2 k + 1) + 6$ — Case 2: $n$ odd.
5
$= 4 k^{2} + 4 k + 1 + 6 k + 3 + 6 = 4 k^{2} + 10 k + 10$ — Expand and collect.
6
$= 2 (2 k^{2} + 5 k + 5)$ — Take out 2. This is even.
7
$Both cases are even$ — So $n^{2} + 3 n + 6$ is even for all integers $n$ .

Remainders work the same way. If $n$ is not a multiple of 3, there are two cases: $3 k + 1$ and $3 k + 2$ .

Worked example

1
Prove that if $n$ is an integer that is not a multiple of 3, then $n^{2} + 2$ is a multiple of 3.
2
$n = 3 k + 1 : (3 k + 1)^{2} + 2 = 9 k^{2} + 6 k + 3$ — Case 1.
3
$= 3 (3 k^{2} + 2 k + 1)$ — A multiple of 3.
4
$n = 3 k + 2 : (3 k + 2)^{2} + 2 = 9 k^{2} + 12 k + 6$ — Case 2.
5
$= 3 (3 k^{2} + 4 k + 2)$ — A multiple of 3.
6
$Both cases give a multiple of 3$ — So $n^{2} + 2$ is a multiple of 3 when $n$ is not a multiple of 3.

A typical 4-mark question: method marks (M) for setting up each case, accuracy marks (A) for correct algebra. The last A1 needs both cases right plus the conclusion.

Common mistake

Trying $n = 1, 2, 3, \dots$ when the question says “use algebra”. That scores no marks.

Common mistake

Choosing $3 k - 1$ and $3 k + 2$ . They are the same case (remainder 2). Use $3 k + 1$ and $3 k + 2$ , or $3 k - 1$ and $3 k + 1$ .

Key idea

Split into cases that cover every integer, prove each one, then finish with one sentence that says the statement is true.

Proving an inequality

Some proofs show one expression is always bigger than another. The key fact: a square is never negative.

Rule

(anything)^{2} \geq 0

Worked example

1
Prove that for all $x > 0$ , $x + \frac{1}{x} \geq 2$ .
2
$(x - 1)^{2} \geq 0$ — A square is never negative. True for all $x$ .
3
$x^{2} - 2 x + 1 \geq 0$ — Expand.
4
$x^{2} + 1 \geq 2 x$ — Add $2 x$ to both sides.
5
$x + \frac{1}{x} \geq 2$ — Divide by $x$ . Since $x > 0$ , the sign stays the same. So the statement is true.

How do you find $(x - 1)^{2}$ ? Work backwards on rough paper: multiply by $x$ , move everything to one side, and factorise. Then write the proof forwards.

The condition $x > 0$ matters. Without it, a counter-example breaks the claim.

Worked example

1
Show that $x + \frac{1}{x} \geq 2$ is not true for all non-zero $x$ .
2
$x = - 1 : - 1 + \frac{1}{- 1} = - 2$ — Try a negative value.
3
$- 2 < 2$ — So the statement is not true for all non-zero $x$ .

Common mistake

Ending at $(x - 1)^{2} \geq 0$ with no reason. Write “because a square is never negative”, then go back to the original statement.

Key idea

Reach a square, say why it is never negative, and link back to what you had to prove.

Which method? Read the question

The wording tells you which kind of proof to write.

You see	You do
“Show that … is false” / “by counter-example”	One case: calculation, reason, “so the statement is false”
A few allowed values (positive integers with conditions)	List every case, check each, say these are all the cases
“For all integers $n$ ”, odd or even	Cases $n = 2 k$ and $n = 2 k + 1$ ; take out 2
“Not a multiple of 3”	Cases $3 k + 1$ and $3 k + 2$ ; take out 3
“Use algebra”	No trying values; letters and expansions only
“Prove that … ≥ …”	Reach a square ≥ 0 and give the reason

Common mistake

Leaving out the final sentence. In every type above, the last mark needs a conclusion such as “so the statement is true for all $n$ ”.

Key idea

Counter-example to break a claim. Every case to prove it. Always end with a sentence that answers the question.

Practise proof by exhaustion and counter-example now

Interactive visual aids, then real past-paper questions marked on your working like the exam. Free to start.

Practise free on Lemmara

Real past-paper questions on proof by exhaustion and counter-example

Each with a full worked solution.

All 15 questions on this topic →

Lemmara is an independent study tool, not affiliated with or endorsed by Cambridge International Education or Pearson Edexcel. The lessons and worked examples are Lemmara’s own.