What is exhaustion on a small range?

Prove that every integer n with 1 n 5 satisfies n^2 2^n + 1. Check each: n=1 gives 1 3; n=2 gives 4 5; n=3 gives 9 9; n=4 gives 16 17; n=5 gives 25 33. All five cases hold, so the statement is proved.

EnglandMathsSyllabus dot point

How do you prove a statement is always true, and how do you show one is false?

Structure of mathematical proof including proof by deduction, proof by exhaustion, disproof by counter-example and proof by contradiction, applied to statements about numbers and inequalities.

A focused answer to the Edexcel A-Level Mathematics proof content, covering proof by deduction, proof by exhaustion, disproof by counter-example and proof by contradiction, including the irrationality of root 2 and the infinitude of primes.

Generated by Claude Opus 4.89 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

Edexcel wants you to understand and use the structure of mathematical proof, including proof by deduction, proof by exhaustion, disproof by counter-example, and proof by contradiction (including proving that $\sqrt{2}$ is irrational and that there are infinitely many primes). You must lay out each step logically and finish with a clear conclusion.

The answer

Proof by deduction

You start from known facts or definitions and use algebra and logic to reach the required conclusion. A strong deduction uses general representations, not specific numbers. An even number is written $2n$ and an odd number $2n+1$ , where $n$ is an integer; a multiple of three is $3n$ , and so on.

Proof by exhaustion

You break the statement into a finite number of cases and verify each one. This works only when there are finitely many cases to check.

Disproof by counter-example

To disprove a general statement you only need one example where it fails. The single example must be shown to break the claim explicitly.

Proof by contradiction

You assume the opposite of what you want to prove, then show this assumption forces an impossible result. Two standard proofs you must know are that $\sqrt{2}$ is irrational and that there are infinitely many primes.

Prove that

\sqrt{2}

is irrational

Step 1: Assume the opposite

Contradiction proofs begin by assuming the statement is false. Suppose $\sqrt{2}$ is rational, so we can write $\sqrt{2} = \dfrac{a}{b}$ where $a$ and $b$ are integers in lowest terms, meaning they share no common factor.

Step 2: Derive a relationship between $a$ and $b$

Squaring both sides gives $2 = \dfrac{a^2}{b^2}$ , so $a^2 = 2b^2$ . This tells us $a^2$ is even, and since the square of an odd number is odd, $a$ itself must be even. Write $a = 2c$ for some integer $c$ .

Step 3: Reach the contradiction

Substitute $a = 2c$ into $a^2 = 2b^2$ :

4c^2 = 2b^2 \implies b^2 = 2c^2.

So $b^2$ is even, which again forces $b$ to be even. Both $a$ and $b$ are divisible by $2$ , contradicting the assumption that the fraction was in lowest terms.

Step 4: State the conclusion

The assumption that $\sqrt{2}$ is rational has led to an impossibility, so the assumption must be false. Therefore $\sqrt{2}$ is irrational.

Examples in context

Inequality by deduction. Prove that $a^2 + b^2 \ge 2ab$ for all real $a$ and $b$ . Start from the fact that a square is non-negative: $(a-b)^2 \ge 0$ . Expanding gives $a^2 - 2ab + b^2 \ge 0$ , so $a^2 + b^2 \ge 2ab$ . The key move is recognising the perfect square to deduce the inequality.

Exhaustion on a small range. Prove that every integer $n$ with $1 \le n \le 5$ satisfies $n^2 \le 2^n + 1$ . Check each: $n=1$ gives $1 \le 3$ ; $n=2$ gives $4 \le 5$ ; $n=3$ gives $9 \le 9$ ; $n=4$ gives $16 \le 17$ ; $n=5$ gives $25 \le 33$ . All five cases hold, so the statement is proved.

Try this

Q1. Prove that the sum of two consecutive integers is always odd. [3 marks]

Cue. Use $n$ and $n+1$ ; their sum is $2n+1$ , which is odd. State a clear conclusion.

Q2. Disprove the claim that $2^n + 1$ is prime for all positive integers $n$ . [2 marks]

Cue. Try $n = 3$ : $2^3 + 1 = 9 = 3 \times 3$ , not prime.

Exam-style practice questions

Practice questions written in the style of Pearson Edexcel exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Edexcel 20194 marksProve that the sum of the squares of two consecutive integers is always odd.

Show worked answer →

Let the consecutive integers be $n$ and $n+1$ , where $n$ is an integer (M1 for a general algebraic representation, not specific numbers).

Sum of squares: $n^2 + (n+1)^2 = n^2 + n^2 + 2n + 1 = 2n^2 + 2n + 1$ .

Factor out $2$ : $2(n^2 + n) + 1$ (M1 for reaching the form $2k+1$ ).

Since $n^2 + n$ is an integer, $2(n^2+n)+1$ has the form $2k+1$ , which is odd (A1).

Conclude: the sum of the squares of two consecutive integers is always odd (A1 for an explicit closing statement). Markers reward general terms and a clear conclusion, not numerical testing.

Edexcel 20215 marksProve by contradiction that

\sqrt{2}

is irrational.

Show worked answer →

Assume the opposite: $\sqrt{2}$ is rational, so $\sqrt{2} = \frac{a}{b}$ where $a$ and $b$ are integers with no common factor (M1 for stating the assumption and the lowest-terms condition).

Square both sides: $2 = \frac{a^2}{b^2}$ , so $a^2 = 2b^2$ (M1).

Then $a^2$ is even, so $a$ is even; write $a = 2c$ (A1). Substituting: $4c^2 = 2b^2$ , so $b^2 = 2c^2$ , hence $b$ is even (M1).

Both $a$ and $b$ are even, contradicting that they have no common factor. The assumption is impossible, so $\sqrt{2}$ is irrational (A1 for stating the contradiction and conclusion).

Edexcel 20182 marksDisprove, by counter-example, the statement that

n^2 + n + 11

is prime for all positive integers

n

Show worked answer →

A single counter-example is enough (M1 for choosing a value that breaks the claim).

Try $n = 10$ : $10^2 + 10 + 11 = 100 + 10 + 11 = 121 = 11 \times 11$ , which is not prime (A1).

State that this counter-example disproves the claim. Markers reward exactly one valid counter-example with the factorisation shown; extra examples earn no more credit.

Related dot points

Sources & how we know this

Pearson Edexcel A-Level Mathematics (9MA0) specification — Pearson Edexcel (2017)