Proof: A-level Maths OCR revision notes

1.01

The structure of a proof

What a proof must establish 1.01

Definitions

Conjecture: a statement believed to be true but not yet proved.
Theorem: a statement that has been proved from definitions and previously established results.
Universal statement: a claim of the form 'for all $x$ of this kind, $P (x)$ holds'.
Existential statement: a claim of the form 'there exists an $x$ of this kind for which $P (x)$ holds'.

Key results

A universal statement is proved only by an argument that covers every case at once, and is disproved by exhibiting a single counterexample.
An existential statement is the mirror image: it is proved by exhibiting a single case, and disproved only by a general argument covering every case.
Notation: $A \Rightarrow B$ means ' $A$ implies $B$ '; $A \Leftarrow B$ means ' $A$ is implied by $B$ '; $A ⟺ B$ means both hold, so $A$ and $B$ are equivalent.

Notes

Checking examples can suggest a conjecture and can build confidence, but it never proves a universal claim — this distinction is the whole point of the topic.
Read the quantifier carefully before choosing a method: 'for all' and 'there exists' require opposite kinds of argument.
$A \Rightarrow B$ and $B \Rightarrow A$ are genuinely different claims — proving one direction of an 'if and only if' statement is not the same as proving both.

1.01

Proof by deduction

Proof by deduction 1.01

Definitions

Proof by deduction: an argument starting from agreed definitions or previously established facts and reasoning forward, step by logical step, to the statement being proved.

Key results

Because it works with a general, unspecified integer or real number, deduction establishes the result for every case at once rather than checking cases individually — the standard method whenever the set of cases is infinite.
Standard forms, for $n \in Z$ : even $2 n$ , odd $2 n + 1$ , consecutive integers $n$ and $n + 1$ , a multiple of 3 is $3 n$ .
Example: the sum of two odd integers is even, since $(2 m + 1) + (2 n + 1) = 2 (m + n + 1)$ and $m + n + 1$ is an integer.
Example: $n^{3} - n = (n - 1) n (n + 1)$ is a product of three consecutive integers, so one factor is even and one is a multiple of 3: $n^{3} - n$ is divisible by 6.

Method

State clearly what is being assumed and introduce a general symbol for the object concerned, saying what set it belongs to (for example 'let $n$ be any integer').
Translate the property in the hypothesis into algebra.
Manipulate that algebra, with every step following necessarily from the one before it.
Interpret the final expression back into words, and finish with a sentence stating that the required result has been proved for every such case.

Notes

Never begin by assuming the statement you are asked to prove and then simplifying it to something obviously true — that is circular reasoning, and it earns no credit even when the algebra is correct. Start from the hypothesis and work towards the conclusion.
Each step must be justified by an established rule; 'it can be seen that' is not a justification.
Introducing a genuinely arbitrary, unspecified object (not one with a hidden extra property) is what makes the conclusion apply to every case — silently assuming, say, that $n$ is positive when the claim covers all integers invalidates the whole proof.

Representing integers algebraically 1.01

Key results

Even integer: $2 n$ , where $n \in Z$ .
Odd integer: $2 n + 1$ , where $n \in Z$ .
Two consecutive integers: $n$ and $n + 1$ .
Two consecutive even integers: $2 n$ and $2 n + 2$ ; two consecutive odd integers: $2 n + 1$ and $2 n + 3$ .
A multiple of $3$ is $3 n$ , and every integer is exactly one of $3 n$ , $3 n + 1$ or $3 n + 2$ — the standard way to split a proof about divisibility by $3$ into cases.
To show a number is even, factor a $2$ out of it and observe that the remaining bracket is an integer; to show it is a multiple of $k$ , factor out $k$ in the same way.

Notes

Use different letters for independently chosen integers. Writing 'let the two odd numbers be $2 n + 1$ and $2 n + 1$ ' forces them to be the same number and proves nothing about the general case.
Always state the set the letter belongs to, since the closure properties being used (a sum or product of integers is an integer) depend on it.
For a claim about products or sums of even/odd numbers, expand fully and factor back out to the required form ( $2 \times integer$ or $2 \times integer + 1$ ) — an unfactored expression, however correct, doesn't yet show the number is even or odd.

Proving identities and inequalities 1.01

Definitions

Identity: a statement, written with $\equiv$ , that two expressions are equal for every value of the variable, as opposed to an equation, which holds only for particular values.

Key results

Completing the square is the standard tool for quadratic inequality proofs: any expression written as $(x + p)^{2} + q$ with $q > 0$ is positive for all real $x$ , because a square is never negative.
The single fact $(a - b)^{2} \geq 0$ for all real $a$ and $b$ proves a large family of inequalities; expanding it immediately gives $a^{2} + b^{2} \geq 2 ab$ , with equality exactly when $a = b$ .

Method

To prove an identity, start with one side — usually the more complicated one — and transform it by valid algebraic steps until it becomes the other side.
Work down one column, writing $\equiv$ between successive forms of that one side only.
Finish by stating that the left-hand side has been shown to equal the right-hand side for all values of the variable.

Notes

Do not move terms across an $\equiv$ sign as if solving an equation — that assumes the identity is true, which is what you are trying to prove.
State the equality case when proving an inequality: knowing when $\geq$ becomes $=$ is part of the result.
Working simultaneously on both sides of an identity (rather than one side alone) risks a circular argument, even when every individual step looks valid — stick to transforming one side into the other.

Worked examples

Worked example

Prove by deduction that the sum of any two odd numbers is even.

Show worked solution

Let the two odd numbers be $2 m + 1$ and $2 n + 1$ , where $m, n \in Z$ .

Their sum is:

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

Since $m + n + 1$ is an integer, this sum is $2$ multiplied by an integer, and is therefore even.

This holds for any two odd numbers, so the sum of any two odd numbers is always even.

Worked example

Prove that the difference between the squares of any two consecutive integers is equal to the sum of those two integers, and deduce that this difference is always odd.

Show worked solution

Let the two consecutive integers be $n$ and $n + 1$ , where $n \in Z$ .

The difference of their squares is:

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

Their sum is:

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

which is the same expression, so the difference of the squares equals the sum of the integers for every integer $n$ .

Since $2 n + 1$ is of the standard form for an odd number with $n$ an integer, that common value is always odd.

As a numerical check,

8^{2} - 7^{2} = 64 - 49 = 15

and $7 + 8 = 15$ , which is odd.

Worked example

Prove that:

x^{2} + 6 x + 11 > 0

for all real values of $x$ .

Show worked solution

Complete the square:

x^{2} + 6 x + 11 = (x + 3)^{2} - 9 + 11 = (x + 3)^{2} + 2

For any real $x$ , the square $(x + 3)^{2} \geq 0$ , so:

(x + 3)^{2} + 2 \geq 2 > 0

Hence:

x^{2} + 6 x + 11 > 0

for all real $x$ , with the smallest value $2$ occurring at $x = - 3$ .

As a check by an independent route, the discriminant is:

6^{2} - 4 (1) (11) = 36 - 44 = - 8 < 0

so the parabola has no real roots, and since it opens upwards it lies entirely above the $x$ -axis.

1.01

Proof by exhaustion

Proof by exhaustion 1.01

Definitions

Proof by exhaustion: verifying a statement separately for every case it covers, having first shown that those cases really are all of them.

Key results

Exhaustion is practical only for a small, finite number of cases — for example proving a claim about all integers from $1$ to $5$ inclusive by verifying it directly for each of the five values.
Grouping into a few general classes can make exhaustion work on an infinite set: to show $n^{2}$ never ends in $7$ , note that the last digit of $n^{2}$ depends only on the last digit $b$ of $n$ , and check the ten cases $b = 0, 1, \dots, 9$ , whose squares end in $0, 1, 4, 9, 6, 5, 6, 9, 4, 1$ — never $7$ .

Method

Show that the cases listed genuinely exhaust every possibility.
Verify the statement explicitly for each case, showing the working for each.
Conclude that, since the statement holds in every case and there are no others, it holds in general.

Notes

This method breaks down completely for a statement about an infinite set with no such grouping (such as 'all positive integers'), since infinitely many cases cannot be checked one by one; deduction, not exhaustion, is required whenever the set of cases is unbounded.
Omitting a case invalidates the whole proof, so state the full list of cases before starting to check them.
Choosing the grouping variable carefully (e.g. last digit, or remainder on division by a small number) is the real skill — the wrong grouping can leave infinitely many sub-cases still to check.

Worked example

Prove by exhaustion that every even integer between $4$ and $16$ inclusive can be written as the sum of two prime numbers.

Show worked solution

The even integers in this range are exactly:

4, 6, 8, 10, 12, 14

and $16$ , so checking these seven cases exhausts every possibility.

$4 = 2 + 2$ ; $6 = 3 + 3$ ; $8 = 3 + 5$ ; $10 = 5 + 5$ ; $12 = 5 + 7$ ; $14 = 7 + 7$ ; $16 = 5 + 11$ .

Each right-hand side is a sum of two primes, and every case in the range has been verified, so the statement is proved for all even integers between $4$ and $16$ inclusive.

Note that this argument says nothing whatever about even numbers above $16$ — extending the claim to all even integers greater than $2$ is Goldbach's conjecture, which remains unproved.

1.01

Disproof by counterexample

Disproof by counterexample 1.01

Definitions

Counterexample: a single specific case satisfying the hypothesis of a universal claim but failing its conclusion.

Key results

A universal claim — one asserting that something is true for every case of a certain kind — is disproved by a single counterexample. No amount of successful cases makes a universal claim true, but exactly one failure makes it false, which is why counterexample is the standard and sufficient method for disproof.
' $x^{2} \geq x$ for all real $x$ ' fails at $x = \frac{1}{2}$ : $(\frac{1}{2})^{2} = \frac{1}{4} < \frac{1}{2}$ .
' $2^{n} - 1$ is prime whenever $n$ is prime' fails at $n = 11$ : $2^{11} - 1 = 2047 = 23 \times 89$ .
' $n^{2} + n + 41$ is prime for every positive integer $n$ ' fails at $n = 40$ : $4 0^{2} + 40 + 41 = 1681 = 4 1^{2}$ .

Method

State the specific value or object being tested.
Evaluate both sides, or verify the property, showing the arithmetic explicitly.
State plainly that the claim fails in this case and is therefore false.

Notes

One counterexample is enough; there is no need to find several, nor to explain why the claim fails in general.
The counterexample must genuinely satisfy the claim's hypothesis — a value outside the stated range disproves nothing.
Show the working explicitly for the chosen value on both sides of the claim — asserting 'this doesn't work' without the calculation shown earns no credit.

Finding a counterexample 1.01

Method

Test the small and unusual cases first: $0$ , $1$ , and $- 1$ .
Try negative numbers, fractions and irrational values if the claim allows them — many false claims are true only for positive integers.
Try the boundary of any stated range, and the smallest case the claim's supporting argument would struggle with.
If a pattern-based claim survives these, look for the first case where the pattern's underlying reason breaks down, such as a value at which a factorisation becomes possible.

Notes

A claim that survives many 'ordinary' test cases can still fail just outside the range its author actually checked, so the plausibility of a claim is no guide to its truth.
If a search for a counterexample keeps failing, that is a hint the claim may be true — switch to trying to prove it by deduction, and let the obstruction in the proof suggest where a counterexample might live.
$n = 0$ and $n = 1$ are worth checking first for almost any claim about integers or powers — they collapse many expressions to something trivially easy to evaluate.

Worked example

Show, by counterexample, that the statement 'for all integers $n \geq 0$ , $n^{2} + n + 1$ is prime' is false.

Show worked solution

Try $n = 4$ :

n^{2} + n + 1 = 16 + 4 + 1 = 21 = 3 \times 7

which is not prime.

This single case is a counterexample, so the statement is false.

The claim looks plausible if too few cases are checked, since $n = 1, 2, 3$ give $3$ , $7$ and $13$ , all prime.

In fact $n = 0$ also fails, since it gives $0 + 0 + 1 = 1$ , and $1$ is not prime by definition — so the smallest counterexample is $n = 0$ , with $n = 4$ the smallest counterexample giving a genuinely composite value.

1.01

Proof by contradiction

Proof by contradiction 1.01

Definitions

Proof by contradiction: assuming the negation of the statement to be proved, deriving a logical impossibility from that assumption, and concluding that the original statement must be true.

Key results

Contradiction proves the classical impossibility results of elementary mathematics: that $2$ is irrational, and that there are infinitely many prime numbers.
For the infinitude of primes: assume there are finitely many, $p_{1}, p_{2}, \dots, p_{k}$ ; the number $N = p_{1} p_{2} \dots p_{k} + 1$ leaves remainder $1$ on division by each of them, so it has a prime factor not on the list — contradicting the assumption that the list was complete.

Method

Write down the negation of the statement carefully — the negation of 'for all $x$ , $P (x)$ ' is 'there exists an $x$ with $P (x)$ false'.
Assume that negation and reason deductively from it.
Reach a contradiction: a statement that conflicts with the assumption itself or with an established fact.
Conclude that the assumption is impossible, so the original statement holds.

Notes

The contradiction must be stated explicitly; a proof that stops at the surprising conclusion without naming what it contradicts is incomplete.
Contradiction is the natural method for claims of the form 'no such object exists' or 'this quantity is irrational', where there is nothing concrete to construct.
For the classic $2$ proof, the key step assumes $\frac{p}{q}$ is already in its lowest terms — without that assumption the argument that $p$ and $q$ share a common factor never yields the needed contradiction.

Worked example

Prove by contradiction that $2$ is irrational.

Show worked solution

First note the lemma that if $a^{2}$ is even then $a$ is even: if $a$ were odd, $a = 2 m + 1$ would give:

a^{2} = 4 m^{2} + 4 m + 1 = 2 (2 m^{2} + 2 m) + 1

which is odd.

Now assume, for contradiction, that $2$ is rational, so:

2 = \frac{a}{b}

where $a, b \in Z$ , $b \neq = 0$ , and the fraction is in its lowest terms, so $a$ and $b$ have no common factor.

Squaring gives:

2 = \frac{a ^{2}}{b ^{2}}

so $a^{2} = 2 b^{2}$ .

Then $a^{2}$ is even, so by the lemma $a$ is even; write $a = 2 k$ with $k \in Z$ .

Substituting, $4 k^{2} = 2 b^{2}$ , so $b^{2} = 2 k^{2}$ , meaning $b^{2}$ is even and hence, by the lemma again, $b$ is even.

But then $a$ and $b$ share the factor $2$ , contradicting the assumption that the fraction was in its lowest terms.

The assumption is therefore impossible, so $2$ cannot be written as a ratio of integers and is irrational.

1.01

Writing up a proof

Writing up a proof 1.01

Key results

A model write-up: 'Let $n \in Z$ . Then $(n + 1)^{2} - n^{2} = 2 n + 1$ , which is odd because $2 n$ is even. Hence the difference between the squares of two consecutive integers is always odd.'
$\Rightarrow$ ('implies') runs one way only; use $\Leftrightarrow$ only when every step reverses. $∴$ means 'therefore'.

Notes

Define every symbol before using it, and state the set it ranges over, for example 'let $m, n \in Z$ '.
Give the reason alongside each non-obvious step; a chain of unexplained equalities is a calculation, not a proof.
Do not use the result being proved anywhere inside the argument.
End with a concluding sentence in words that restates exactly what has been shown, including the range of cases it covers — marks are routinely lost for a correct calculation with no conclusion.
Check that the proof actually uses every hypothesis given; if it does not, either the argument has a gap or the hypothesis was unnecessary, and both are worth noticing.
Read back through the finished proof as if seeing it for the first time — a genuinely independent reader should be able to follow every step without having to guess what was intended.