A proof is a chain of logical steps that starts from things you already know to be true and ends at the statement you want to establish. Once a result is proved, it is true for ever and in every case — no amount of checking examples can do that.
$\Downarrow$ a sequence of valid logical steps $\Downarrow$
Conclusion (exactly the statement you were asked to prove)
In the first year of A Level you meet three methods (DfE content area A · Proof):
| Method | What you do | Typical use |
|---|---|---|
| Proof by deduction | Start from general facts and argue step by step to the result, usually with algebra. | "Prove that the sum of any two odd numbers is even." |
| Proof by exhaustion | Split the situation into a finite number of cases and check every one. | "Prove that every square number leaves remainder 0 or 1 when divided by 3." |
| Disproof by counter-example | Find one case where a claim fails. | "Show that '$n^2 + n + 41$ is always prime' is false." |
The subject content expects you to understand and use the standard notation of logic and sets. These symbols appear in exam questions and you should use them in your own proofs.
| Symbol | Read as | Example |
|---|---|---|
| $\Rightarrow$ | "implies" — if the left is true, the right must be true | $x = 3 \Rightarrow x^2 = 9$ |
| $\Leftarrow$ | "is implied by" — if the right is true, the left must be true | $x^2 = 9 \Leftarrow x = -3$ |
| $\Leftrightarrow$ | "if and only if" — each implies the other | $2x + 1 = 7 \Leftrightarrow x = 3$ |
| $\therefore$ | "therefore" | $n = 2k$ $\therefore$ $n$ is even |
| $\in$, $\notin$ | "is a member of", "is not a member of" | $5 \in \mathbb{Z}$, $\tfrac12 \notin \mathbb{Z}$ |
| $\mathbb{N}$ | the natural numbers $\{1, 2, 3, \dots\}$ | $7 \in \mathbb{N}$ |
| $\mathbb{Z}$ | the integers $\{\dots, -2, -1, 0, 1, 2, \dots\}$ | $-4 \in \mathbb{Z}$ |
| $\mathbb{Q}$ | the rational numbers — anything that can be written $\dfrac{p}{q}$ with $p, q \in \mathbb{Z}$, $q \neq 0$ | $0.75 = \tfrac34 \in \mathbb{Q}$ |
| $\mathbb{R}$ | the real numbers — every point on the number line | $\sqrt{2} \in \mathbb{R}$, $\pi \in \mathbb{R}$ |
| $\equiv$ | "is identically equal to" — true for every value | $(x+1)^2 \equiv x^2 + 2x + 1$ |
Implication goes one way
"$A \Rightarrow B$" does not mean "$B \Rightarrow A$". The reverse statement is called the converse, and it may be false.
Write $\Rightarrow$, $\Leftarrow$ or $\Leftrightarrow$ between each pair of statements.
Examiners mark proofs on completeness and clarity, not just on whether the algebra is right. A good proof follows the same pattern every time.
- State your assumptions. Define every letter: "Let $n$ be any integer." "Let the two odd numbers be $2m+1$ and $2n+1$, where $m, n \in \mathbb{Z}$."
- Work in logical steps. Each line must follow from the ones before. Use $\Rightarrow$ or words such as "so" and "therefore" to link them.
- Use general letters, not numbers. A proof about "any odd number" must work for $2n + 1$, not just for $7$.
- Reach the exact statement you were asked to prove. If you need to show something is a multiple of $3$, your last line must be of the form $3 \times (\text{an integer})$.
- Write a concluding sentence. For example: "Therefore the sum of any two odd numbers is even." Many mark schemes give the final mark only for this.
Consecutive integers: $n,\; n+1,\; n+2$ · Consecutive odd numbers: $2n+1,\; 2n+3$
Prove that the sum of any two odd numbers is even.
Prove that $(n + 3)^2 - (n - 3)^2 \equiv 12n$.
Content area A in the first year, and the page that covers each part.
- AProof by Deduction and ExhaustionAlgebraic proofs with odd, even and consecutive integers; completing the square to prove an expression is positive; proving identities; checking every case.
- ADisproof by Counter-exampleShowing that a general statement is false by finding a single case where it fails.
$A \Rightarrow B$
If $A$ is true then $B$ is true. Says nothing about the converse.
$A \Leftrightarrow B$
$A$ and $B$ are either both true or both false.
Number sets
$\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}$
Even / odd
$2n$ and $2n+1$ for $n \in \mathbb{Z}$.
Deduction
General algebra from known facts to the result.
Exhaustion
Finitely many cases — check every one.
Counter-example
One failure is enough to disprove a claim.
Identity
Start from one side; transform it into the other.
Finish
End with a sentence stating what has been proved.
Ten questions drawing on the whole Proof topic. Work each one through before opening the solution.
For each number, list every set from $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$ that it belongs to: (a) $-6$ (b) $0.\dot{3}$ (c) $\sqrt{5}$ (d) $\sqrt{49}$
▶ Show solution
(a) $-6 \in \mathbb{Z}, \mathbb{Q}, \mathbb{R}$ (negative, so not in $\mathbb{N}$).
(b) $0.\dot{3} = \tfrac13$, so $0.\dot{3} \in \mathbb{Q}, \mathbb{R}$.
(c) $\sqrt{5}$ is irrational: $\sqrt{5} \in \mathbb{R}$ only.
(d) $\sqrt{49} = 7$, so it belongs to all four: $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$.
Write $\Rightarrow$, $\Leftarrow$ or $\Leftrightarrow$ in each box. (a) $x > 5 \;\square\; x > 2$ (b) $x^2 - 7x + 10 = 0 \;\square\; x = 2 \text{ or } x = 5$ (c) $x = -3 \;\square\; x^2 = 9$
▶ Show solution
(a) $\Rightarrow$. Any number bigger than $5$ is bigger than $2$, but $x = 3$ satisfies $x > 2$ and not $x > 5$.
(b) $\Leftrightarrow$, since $x^2 - 7x + 10 = (x-2)(x-5)$.
(c) $\Rightarrow$. $x = -3$ gives $x^2 = 9$, but $x^2 = 9$ could mean $x = 3$.
Write down the converse of "If $n$ is a multiple of $6$, then $n$ is a multiple of $3$." Is the converse true?
▶ Show solution
Converse: "If $n$ is a multiple of $3$, then $n$ is a multiple of $6$."
This is false: $n = 9$ is a multiple of $3$ but not of $6$. (The original statement is true: $n = 6k = 3(2k)$.)
Prove that the product of any two odd numbers is odd.
▶ Show solution
Let the numbers be $2m + 1$ and $2n + 1$ with $m, n \in \mathbb{Z}$.
$(2m+1)(2n+1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1$
$2mn + m + n$ is an integer, so the product has the form $2k + 1$ with $k \in \mathbb{Z}$.
Therefore the product of any two odd numbers is odd.
Prove that $(2n + 1)^2 - (2n - 1)^2$ is a multiple of $8$ for every integer $n$.
▶ Show solution
$(2n+1)^2 - (2n-1)^2 = \left(4n^2 + 4n + 1\right) - \left(4n^2 - 4n + 1\right) = 8n$
$n$ is an integer, so $8n$ is a multiple of $8$.
Therefore the difference of the squares of any two consecutive odd numbers is a multiple of $8$.
Prove that $x^2 - 6x + 10 > 0$ for all real values of $x$.
▶ Show solution
Complete the square: $x^2 - 6x + 10 \equiv (x - 3)^2 - 9 + 10 = (x-3)^2 + 1$.
For all real $x$, $(x - 3)^2 \geqslant 0$, so $(x - 3)^2 + 1 \geqslant 1 > 0$.
Therefore $x^2 - 6x + 10 > 0$ for all real $x$.
A student writes: "$x^2 = 5x \;\Rightarrow\; x = 5$. So the only solution of $x^2 = 5x$ is $x = 5$." Explain the error and give the correct conclusion.
▶ Show solution
The student has divided both sides by $x$, which is only valid if $x \neq 0$. The case $x = 0$ has been lost.
Correctly: $x^2 - 5x = 0 \Leftrightarrow x(x - 5) = 0 \Leftrightarrow x = 0 \text{ or } x = 5$.
Prove by exhaustion that no square number ends in the digit $7$.
▶ Show solution
The last digit of $n^2$ depends only on the last digit of $n$. There are ten cases:
| Last digit of $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Last digit of $n^2$ | 0 | 1 | 4 | 9 | 6 | 5 | 6 | 9 | 4 | 1 |
In every case the last digit is $0, 1, 4, 5, 6$ or $9$ — never $7$.
Since every integer falls into exactly one of these cases, no square number ends in $7$.
Disprove the statement "$n^2 + n + 41$ is prime for every positive integer $n$."
▶ Show solution
Try $n = 40$: $40^2 + 40 + 41 = 1600 + 40 + 41 = 1681 = 41^2$.
$1681 = 41 \times 41$ is not prime, so $n = 40$ is a counter-example and the statement is false.
(The formula does give primes for $n = 1, 2, \dots, 39$ — a famous warning that many examples do not make a proof. $n = 41$ also works as a counter-example: $41^2 + 41 + 41 = 41 \times 43$.)
(a) Prove that the sum of any three consecutive integers is a multiple of $3$.
(b) Prove that the sum of any four consecutive integers is never a multiple of $4$.
(c) A student claims that "the sum of any $k$ consecutive integers is a multiple of $k$." Disprove this claim.
▶ Show solution
(a) Let the integers be $n, n+1, n+2$ with $n \in \mathbb{Z}$.
Sum $= 3n + 3 = 3(n + 1)$, and $n + 1 \in \mathbb{Z}$, so the sum is a multiple of $3$.
(b) Let the integers be $n, n+1, n+2, n+3$.
Sum $= 4n + 6 = 4(n + 1) + 2$.
This is $2$ more than a multiple of $4$, so it always leaves remainder $2$ when divided by $4$. Therefore it is never a multiple of $4$.
(c) Part (b) already shows the claim fails for $k = 4$: for example $1 + 2 + 3 + 4 = 10$, which is not a multiple of $4$.
A simpler counter-example is $k = 2$: $1 + 2 = 3$, which is not a multiple of $2$. One counter-example is enough, so the claim is false.