Notes · MathematicsUK · A-Levels

Proof

Proof is the discipline of establishing mathematical truth beyond doubt. The A-Level requires four techniques: proof by deduction, proof by exhaustion, disproof by counter-example and proof by contradiction. Each is a distinct tool, and part of the skill is choosing the right one for a given claim.

4 sections~12 min reading time3 competenciesLevel Standard 3 · Advanced 1

T·0222 / 20

Exam profile

AO2 · Construct and present rigorous mathematical arguments and proofsAO1 · Use algebraic manipulation accurately within a proofAO2 · Understand and use the logical structure of a mathematical statement, its converse and negation

Operators:proveshow thatdeducedisproveverifyexplain

basic level

AS-Level expects deduction, exhaustion and disproof by counter-example on short, self-contained claims.

higher level

The full A-Level adds proof by contradiction, including the standard results that $\sqrt{2}$ is irrational and that there are infinitely many primes.

Depth

Text

Contents · 4 sections

Proof

The language and structure of proof#

StandardDfE GCE Mathematics AAQA 7357 A

The structure of a proof

Fig. 1Each node follows necessarily from those before it; the chain ends at the required conclusion.

A proof is a finite sequence of statements, each of which is either a given hypothesis, a definition, a previously established result, or a logical consequence of earlier statements, ending with the claim to be proved. What makes it a proof rather than an argument is that no step relies on intuition, on a picture, or on checking examples: every line must be justified. Learning to write in this style is the single most transferable skill in the whole qualification.

Every claim has a precise logical form, and identifying it tells you what you must do. A statement of the form 'if

P

then

Q

' (written

P \Rightarrow Q

) is proved by assuming

P

and deducing

Q

. Its converse is

Q \Rightarrow P

, which is a different statement that may be true or false independently. Its negation is 'P is true but Q is false'; producing a single case of the negation disproves the original. The contrapositive 'if not

Q

then not

P

' is logically equivalent to the original and is sometimes easier to prove.

Definitions must be stated algebraically before you can reason with them. An even integer is one of the form

2k

for some integer

k

; an odd integer is

2k + 1

; an integer

a

is a multiple of

n

a = nk

for some integer

k

; a rational number is one expressible as

\dfrac{p}{q}

with

p, q

integers and

q \neq 0

. Almost every number-theoretic proof begins by writing the objects in one of these standard forms.

Finally, a proof must be general. If a claim is about 'every integer

n

', your working must use a symbol

n

that could be any integer, never a specific value. Substituting

n = 5

to 'check' is a verification, not a proof; conversely, to disprove a universal claim you need only one counter-example. Keeping this asymmetry clear — one counter-example refutes, but no list of examples confirms — underlies the whole topic.

P \Rightarrow Q \quad\text{is equivalent to}\quad (\neg Q) \Rightarrow (\neg P)

A statement and its contrapositive

The contrapositive has the same truth value as the original implication, so proving one proves the other.

Worked example

Reading the logical structure

A student claims: 'if a number is divisible by 6 then it is divisible by 3, so if a number is divisible by 3 then it is divisible by 6.' Explain the error and give a counter-example.

Identify the forms
The true statement is $P \Rightarrow Q$ with $P$ : 'divisible by 6' and $Q$ : 'divisible by 3'. The student then asserts $Q \Rightarrow P$ , the converse.
Explain
An implication does not guarantee its converse; they are logically independent.
Counter-example
$9$ is divisible by 3 but not by 6, so $Q \Rightarrow P$ is false.

Result: The student has assumed the converse; $9$ is a counter-example, so the converse is false.

Typical mistakes

Proving the converse instead of the stated implication.
Using a specific value of $n$ and calling the resulting verification a proof.

Active revision

Write down the converse, the negation and the contrapositive of the statement: 'if $n^2$ is odd then $n$ is odd.' State which of the three is logically equivalent to the original.

Active recall

Recall the key points — then reveal.

Sources: Mathematics: AS and A level content (GCE subject content) (Department for Education) · AQA A-level Mathematics 7357 specification (AQA)

Proof by deduction#

StandardDfE GCE Mathematics AAQA 7357 A

Exterior angle of a triangle

Fig. 2A deductive geometric proof: the exterior angle ACD equals angle A plus angle B.

Proof by deduction is the workhorse technique: you start from accepted facts and definitions and proceed by valid algebraic and logical steps to the required conclusion. It is 'direct' in that you assume the hypothesis and drive straight towards the conclusion. The great majority of 'prove that' and 'show that' questions in the pure papers are deductive.

The method for number results is almost always to write the general object in standard form and manipulate. To prove that the product of two odd numbers is odd, take two odd numbers

2m + 1

and

2n + 1

; their product is

4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1

, which is of the form

2k + 1

and hence odd. The key move is factoring out the 2 to expose the structure the definition demands.

Deduction is equally the language of geometry, where each step cites a named result. To prove the exterior angle of a triangle equals the sum of the two interior opposite angles, you use that the three interior angles sum to

180^\circ

and that angles on a straight line sum to

180^\circ

; subtracting the shared interior angle from both gives the result. Every geometric step must be justified by a stated theorem, never by measurement of the diagram.

A recurring style is 'show that', where the target expression is printed. Here the marks lie entirely in the intermediate reasoning, so you must show every manipulation and end with exactly the printed form. Working towards a given answer is legitimate, but you must not assume the very thing you are proving as a starting line.

(2m+1)(2n+1) = 2(2mn + m + n) + 1

Product of two odd numbers

The right-hand side has the form $2k+1$ , proving the product is odd for all integers $m, n$ .

Worked example

A direct number proof

Prove that for all integers $n$ , the expression $n^2 + n$ is even.

Factorise
$n^2 + n = n(n + 1)$ , the product of two consecutive integers.
Argue about parity
Of any two consecutive integers, exactly one is even, so their product is a multiple of 2.
Conclude
Hence $n(n+1) = 2k$ for some integer $k$ , so $n^2 + n$ is even for every integer $n$ .

Result: $n^2 + n = n(n+1)$ is a product of consecutive integers and is therefore even for all integers $n$ .

Typical mistakes

Assuming the statement to be proved (circular reasoning) instead of deriving it.
Stopping one algebraic step short of the required form, e.g. leaving $4mn + 2m + 2n + 1$ without factoring out the 2.

Active revision

Prove by deduction that the sum of the squares of two consecutive integers is always odd.

Active recall

Recall the key points — then reveal.

Sources: Mathematics: AS and A level content (GCE subject content) (Department for Education) · AQA A-level Mathematics 7357 specification (AQA)

Proof by exhaustion and disproof by counter-example#

StandardDfE GCE Mathematics AAQA 7357 A

A counter-example to a plausible claim

Fig. 3The claim 'n^2 + n + 41 is always prime' is false: n = 40 gives 41 x 41.

Proof by exhaustion establishes a claim by splitting the possibilities into a finite number of cases and verifying the claim in each. It is valid only when the cases genuinely cover every possibility. For example, to prove that every integer square leaves remainder 0 or 1 on division by 4, consider the two cases

n = 2k

(giving

n^2 = 4k^2

, remainder 0) and

n = 2k + 1

(giving

n^2 = 4k^2 + 4k + 1

, remainder 1); since every integer is even or odd, these cases are exhaustive.

The art of exhaustion is choosing the right partition. Splitting the integers by their remainder on division by a small number (their residue class) is the commonest device, because it converts an infinite claim into finitely many algebraic checks. Whenever you use exhaustion you must state explicitly that the cases cover all possibilities, or the proof is incomplete.

Disproof by counter-example is the mirror image: to show a universal statement is false, you exhibit one instance where it fails. Because a universal claim asserts something about every object, a single failure destroys it. The famous instance is

n^2 + n + 41

, which is prime for

n = 0, 1, 2, \ldots, 39

but not for

n = 40

, where it equals

41^2

. This shows dramatically that no amount of confirming evidence proves a general claim.

The two techniques are natural partners: exhaustion proves a claim by checking all cases, while a counter-example refutes one by finding a single bad case. When a question says 'prove or disprove', you must first decide which is true, then supply either an exhaustive argument or one clean counter-example — never a vague appeal to 'lots of examples'.

Worked example

Proof by exhaustion on residues

Prove that $n^3 - n$ is divisible by 3 for every integer $n$ .

Factorise
$n^3 - n = n(n-1)(n+1)$ , the product of three consecutive integers.
Split into cases mod 3
Every integer is $3k$ , $3k+1$ or $3k+2$ . In the first case $n$ is a multiple of 3; in the second $n-1 = 3k$ is; in the third $n+1 = 3(k+1)$ is.
Conclude
In all three exhaustive cases one factor is a multiple of 3, so the product $n(n-1)(n+1)$ is divisible by 3.

Result: $n^3 - n = n(n-1)(n+1)$ contains a multiple of 3 in every case, so it is divisible by 3 for all integers $n$ .

Typical mistakes

Using cases that do not cover every possibility, so the exhaustion is incomplete.
Trying to 'prove' a false universal statement instead of testing small cases to find the counter-example.

Active revision

Prove by exhaustion that the square of any integer is either a multiple of 3 or one more than a multiple of 3. Then disprove: 'for all positive integers $n$ , $2^n - 1$ is prime.'

Active recall

Recall the key points — then reveal.

Sources: Mathematics: AS and A level content (GCE subject content) (Department for Education) · AQA A-level Mathematics 7357 specification (AQA)

Proof by contradiction#

AdvancedDfE GCE Mathematics AAQA 7357 A

Locating the irrational number root 2

Fig. 4The positive root of

x^2 = 2

\sqrt{2}

; the proof shows this value cannot be written as a fraction.

Proof by contradiction (reductio ad absurdum) proves a statement by assuming its negation and deriving a logical impossibility. Because a statement and its negation cannot both hold, the impossibility forces the negation to be false, and hence the original statement to be true. It is the required technique for claims of the form 'no object has this property' or where a direct approach has no obvious starting point.

The archetype is the irrationality of

\sqrt{2}

. Assume, for contradiction, that

\sqrt{2}

is rational, so

\sqrt{2} = \dfrac{p}{q}

in lowest terms (so

p

and

q

share no common factor). Squaring gives

p^2 = 2q^2

, so

p^2

is even, hence

p

is even, say

p = 2r

. Then

4r^2 = 2q^2

, so

q^2 = 2r^2

is even and

q

is even too. But then

p

and

q

share the factor 2, contradicting 'lowest terms'. The assumption is impossible, so

\sqrt{2}

is irrational.

Euclid's proof that there are infinitely many primes is the second set text. Assume there are only finitely many primes

p_1, p_2, \ldots, p_n

. Consider

N = p_1 p_2 \cdots p_n + 1

. Dividing

N

by any

p_i

leaves remainder 1, so no listed prime divides

N

; yet

N > 1

has a prime factor. This factor is a prime not in the list, contradicting the assumption that the list was complete. Hence no finite list can contain all primes.

The discipline of the method is to state clearly 'assume, for contradiction, that ...', to reason validly to a definite contradiction, and to conclude that the assumption was false. The contradiction must be genuine — two statements that cannot both be true — not merely something surprising. Setting up the negation correctly (for instance, the negation of 'irrational' is 'can be written as

p/q

in lowest terms') is where most marks are won or lost.

\sqrt{2} = \frac{p}{q} \ \Rightarrow\ p^2 = 2q^2

The key algebraic step

Assuming rationality in lowest terms and squaring forces both $p$ and $q$ to be even, contradicting 'lowest terms'.

Worked example

Irrationality by contradiction

Prove that $\sqrt{3}$ is irrational.

Assume the negation
Suppose $\sqrt{3}$ is rational, so $\sqrt{3} = \dfrac{p}{q}$ with integers $p, q$ having no common factor and $q \neq 0$ .
Square and deduce a factor
Then $p^2 = 3q^2$ , so $p^2$ is a multiple of 3, hence $p$ is a multiple of 3; write $p = 3r$ .
$p^2 = 3q^2$
Reach the contradiction
Substituting, $9r^2 = 3q^2$ , so $q^2 = 3r^2$ ; thus $q$ is also a multiple of 3. Then $p$ and $q$ share the factor 3, contradicting 'no common factor'.
Conclude
The assumption is impossible, so $\sqrt{3}$ is irrational.

Result: Assuming $\sqrt{3} = p/q$ in lowest terms forces 3 to divide both $p$ and $q$ , a contradiction; hence $\sqrt{3}$ is irrational.

Typical mistakes

Negating the statement incorrectly, so the argument never reaches a genuine contradiction.
Forgetting the 'lowest terms' assumption, which is precisely what the contradiction violates.

Active revision

Prove by contradiction that there is no smallest positive rational number.

Active recall

Recall the key points — then reveal.

Sources: Mathematics: AS and A level content (GCE subject content) (Department for Education) · AQA A-level Mathematics 7357 specification (AQA)

References & sources

Sources

Department for Education

Mathematics: AS and A level content (GCE subject content)

AQA

AQA A-level Mathematics 7357 specification

Proof

4 sections~12 min reading time3 competenciesLevel Standard 3 · Advanced 1

Proof

Key points

Reading the logical structure

Key points

A direct number proof

Key points

Proof by exhaustion on residues

Key points

Irrationality by contradiction

Sources

Proof

Key points

Reading the logical structure

Key points

A direct number proof

Key points

Proof by exhaustion on residues

Key points

Irrationality by contradiction

Sources