Structure of proof and proof by exhaustionEdexcel International A Level Maths: Revision notes

Section 1

What a proof is

A proof is a logical argument that starts from given assumptions and moves through a series of steps, each following from the one before, to a conclusion. Every step must be justified, and the conclusion must be the statement you set out to prove.

A good proof has a clear structure:

state what is being proved, and the values or type of number it applies to
state any assumptions or definitions you are using
show each logical step
finish with a clear conclusion, in words, that links back to the statement.

A few examples that agree with a statement do not prove it. To prove a statement for a set of cases, you must deal with every case in that set.

Key termsproofassumptionconclusion

Common mistake

Writing a conclusion that does not say what has been proved, such as ending with a list of numbers. Write a sentence that answers the original statement.

Section 2

Proof by exhaustion

Proof by exhaustion means proving a statement by checking every possible case and showing that it is true in each one. It is only possible when there is a finite (small enough) number of cases.

The method:

List every case allowed by the conditions of the statement.
Check the statement for each case.
Conclude: the statement is true because it holds in every case.

If even one case fails, the statement is false, and the failing case shows why.

Key termsproof by exhaustioncasefinite

Exam tip

Count the cases before you start. If you cannot list them all, exhaustion is not the right method.

Section 3

Worked example: sums of odd integers

Statement: if $x$ and $y$ are odd positive integers less than $7$ , then $x+y$ is divisible by $2$ .

The only possible values of each of $x$ and $y$ are $1,3,5$ . The possible sums are $1+1=2,\ 1+3=4,\ 1+5=6,\ 3+3=6,\ 3+5=8,\ 5+5=10.$ Each sum is divisible by $2$ . Every possible case has been checked, so $x+y$ is divisible by $2$ whenever $x$ and $y$ are odd positive integers less than $7$ .

Because $x+y=y+x$ , you may list each unordered pair once, but you must say that you are doing so.

Key termsdivisible

Common mistake

Leaving out a case, such as $(5,5)$ or $(3,3)$ where both numbers are equal. Work through the list systematically.

Section 4

Worked example: evaluating an expression

Statement: for every integer $n$ with $1\le n\le5$ , $n^2+n$ is even.

$n$	1	2	3	4	5
$n^2+n$	2	6	12	20	30

All five values are even, so the statement is true for every integer from $1$ to $5$ .

Setting out a table shows the examiner that every case has been done. Show the calculation for each case, not just the answer.

Key termsstatement

Exam tip

Write the conclusion in the context of the question: 'so $n^2+n$ is even for every integer $n$ with $1\le n\le5$ '.

Section 5

Limits of exhaustion

Proof by exhaustion works only when the list of cases is finite and checkable. It cannot prove a statement about all integers, because there are infinitely many cases and you cannot check them all.

Checking $n=3,5,7,9$ shows that $n^2-1$ is a multiple of $8$ for those values only. It says nothing about $n=11$ or $n=101$ .

If a statement is false for one case in the list, that case is enough to show it is false. For example, $n^2+n+11$ is prime for $n=0,1,\ldots,9$ but $n=10$ gives $121=11^2$ , so the statement 'prime for $0\le n\le10$ ' is false.

Key termsinfinitelimit of the method

Common mistake

Claiming that a statement holds for all integers because it works for the first few. Examples that agree are not a proof.

That's the notes covered.

Carry on to the next subtopic.

Exam questions on Structure of proof and proof by exhaustion

A statement S is made: for every integer $n$ with $1\le n\le5$ , the value of $n^2+n$ is even.
Prove that S is true by exhaustion.2 marks
$x$ and $y$ are odd positive integers, each less than 7.
Prove that $x+y$ is divisible by $2$ for every possible pair.2 marks
Let $f(n)=n^3-n$ , where $n$ is an integer.
Use proof by exhaustion to show that $f(n)$ is divisible by $6$ for every integer $n$ with $2\le n\le6$ .3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).