A proof is a chain of logical steps that shows a statement is true in every case it claims to cover. Checking examples, however many, is not a proof: it only shows that the statement has not failed yet.
Use methods of proof, including proof by deduction, proof by exhaustion, disproof by counter-example, and proof by contradiction
| Word or symbol | Meaning | Example |
|---|---|---|
| Statement | A sentence that is either true or false. | "$17$ is prime." |
| Conjecture | A statement believed to be true but not yet proved. | "Every even number greater than $2$ is the sum of two primes." |
| Theorem | A statement that has been proved. | Pythagoras' theorem |
| $\Rightarrow$ | "implies": if the left is true, so is the right. | $x = 3 \Rightarrow x^2 = 9$ |
| $\Leftarrow$ | "is implied by". | $x^2 = 9 \Leftarrow x = -3$ |
| $\Leftrightarrow$ | "if and only if": each implies the other. | $2x + 1 = 7 \Leftrightarrow x = 3$ |
| Negation | The statement that is true exactly when the original is false. | "$n$ is even" negates to "$n$ is odd" (for integers) |
| $\mathbb{Z},\ \mathbb{Q},\ \mathbb{R}$ | Integers, rational numbers, real numbers. | $\tfrac{3}{4} \in \mathbb{Q}$, $\sqrt{2} \notin \mathbb{Q}$ |
| Rational | Can be written $\dfrac{a}{b}$ with $a, b \in \mathbb{Z}$ and $b \neq 0$. | $0.125 = \tfrac{1}{8}$ |
| Irrational | Real, but not rational. | $\sqrt{2}$, $\pi$, $\mathrm{e}$ |
The first three are recapped in full on the Year 1 page Proof Overview.
Prove that the difference between the squares of two consecutive odd numbers is a multiple of $8$.
Prove that no square number ends in the digit $7$.
Show that the statement "$2^n - 1$ is prime for every prime $n$" is false.
Some statements are hard to attack directly because they say something cannot happen, or that something goes on for ever. "$\sqrt{2}$ is not a fraction." "There is no largest prime." There is no obvious first line for a deduction. Contradiction gives you one: suppose it can happen, and follow the consequences.
| The statement says… | Usually prove by… |
|---|---|
| "For all integers $n$, an expression is even / a multiple of $k$" | Deduction, often with cases (exhaustion) |
| "For all $n$ from $1$ to $10$…" or "for every digit…" | Exhaustion |
| "Every…" when you suspect it is false | Counter-example |
| "…is irrational", "there are infinitely many…", "there is no largest/smallest…", "…has no integer solutions" | Contradiction |
Prove that there is no largest integer.
The Year 2 page, and the Year 1 pages it builds on.
- AProof by ContradictionNegating a statement, the irrationality of $\sqrt{2}$, infinitely many primes, and results such as $a^2 - 4b \neq 2$.
- Y1Proof by Deduction and ExhaustionDirect algebraic proof, and splitting into cases. (Year 1 recap.)
- Y1Disproof by Counter-exampleOne failing case is enough. (Year 1 recap.)
Even / odd
$2n$ and $2n+1$, with $n \in \mathbb{Z}$.
Deduction
Known facts $\to$ logical steps $\to$ result.
Exhaustion
Finite list of cases that covers everything.
Counter-example
One failure disproves a "for all" statement.
Contradiction
Assume false, reach an impossibility, conclude true.
Rational
$\dfrac{a}{b}$ with $a, b \in \mathbb{Z}$, $b \neq 0$.
$\Rightarrow$ vs $\Leftrightarrow$
Only use $\Leftrightarrow$ if it works both ways.
Finish
A concluding sentence, or $\blacksquare$.
Ten questions using all four methods. Decide which method to use before you start writing.
Prove that the sum of any three consecutive integers is a multiple of $3$.
▶ Show solution
Let the integers be $n$, $n+1$, $n+2$ with $n \in \mathbb{Z}$.
Sum $= 3n + 3 = 3(n+1)$, and $n+1$ is an integer.
So the sum is a multiple of $3$. $\blacksquare$
Show that the statement "if $a > b$ then $a^2 > b^2$" is false.
▶ Show solution
Take $a = 1$, $b = -2$. Then $a > b$.
But $a^2 = 1$ and $b^2 = 4$, so $a^2 < b^2$.
This counter-example shows the statement is false. (It is true when $a$ and $b$ are both non-negative.)
Write down the negation of each statement. (a) "$x$ is irrational." (b) "There are infinitely many prime numbers." (c) "There is a largest even number." (d) "$n^2$ is even." (with $n$ an integer)
▶ Show solution
(a) "$x$ is rational."
(b) "There are finitely many prime numbers."
(c) "There is no largest even number."
(d) "$n^2$ is odd."
Prove that the product of any two odd numbers is odd.
▶ Show solution
Let the odd numbers be $2m+1$ and $2n+1$, where $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$ and is odd. $\blacksquare$
Prove by exhaustion that $n^3 - n$ is a multiple of $3$ for every integer $n$.
▶ Show solution
Factorise: $n^3 - n = (n-1)n(n+1)$. Every integer is $3k$, $3k+1$ or $3k+2$.
$n = 3k$: the factor $n$ is a multiple of $3$.
$n = 3k + 1$: the factor $n - 1 = 3k$ is a multiple of $3$.
$n = 3k + 2$: the factor $n + 1 = 3k + 3 = 3(k+1)$ is a multiple of $3$.
In every case one factor is a multiple of $3$, so $n^3 - n$ is too. $\blacksquare$
Prove by contradiction that there is no smallest positive rational number.
▶ Show solution
Assume there is a smallest positive rational number, $q$.
Then $\dfrac{q}{2}$ is also rational (if $q = \tfrac{a}{b}$ then $\tfrac{q}{2} = \tfrac{a}{2b}$) and positive.
But $\dfrac{q}{2} < q$, contradicting the assumption that $q$ is the smallest.
So there is no smallest positive rational number. $\blacksquare$
Prove that $x^2 - 6x + 10 > 0$ for all real $x$.
▶ Show solution
Complete the square: $x^2 - 6x + 10 = (x - 3)^2 + 1$.
$(x-3)^2 \geqslant 0$ for all real $x$, so $(x-3)^2 + 1 \geqslant 1 > 0$. $\blacksquare$
Ali claims that "$n^2 + n + 41$ is prime for every positive integer $n$." He has checked $n = 1$ to $n = 10$. Explain why this does not prove the claim, and show that the claim is false.
▶ Show solution
Checking ten cases says nothing about the infinitely many other positive integers.
Take $n = 41$: $41^2 + 41 + 41 = 41(41 + 1 + 1) = 41 \times 43$, which is not prime.
So $n = 41$ is a counter-example. (In fact $n = 40$ also works: $40^2 + 40 + 41 = 1681 = 41^2$.)
Prove by contradiction that there are no integers $a$ and $b$ for which $6a + 9b = 1$.
▶ Show solution
Assume there are integers $a$ and $b$ with $6a + 9b = 1$.
Then $3(2a + 3b) = 1$, so $2a + 3b = \dfrac{1}{3}$.
But $2a + 3b$ is an integer and $\tfrac{1}{3}$ is not — a contradiction.
So no such integers exist. $\blacksquare$
(a) Prove that, for any integer $n$, $n^2$ leaves a remainder of $0$ or $1$ when divided by $4$. (b) Hence prove by contradiction that no integer of the form $4k + 3$ can be written as the sum of two square numbers. (c) Find the smallest positive integer of the form $4k + 1$ that is not the sum of two squares (where $0$ counts as a square), and explain what this shows about the statement "every number of the form $4k+1$ is a sum of two squares".
▶ Show solution
(a) (Exhaustion.) If $n = 2m$ then $n^2 = 4m^2$, remainder $0$.
If $n = 2m + 1$ then $n^2 = 4m^2 + 4m + 1 = 4(m^2 + m) + 1$, remainder $1$. $\blacksquare$
(b) Assume $4k + 3 = a^2 + b^2$ for some integers $a, b, k$.
By (a), $a^2$ and $b^2$ each leave remainder $0$ or $1$ on division by $4$, so $a^2 + b^2$ leaves remainder $0$, $1$ or $2$.
But $4k + 3$ leaves remainder $3$ — a contradiction. So no such $a$, $b$ exist. $\blacksquare$
(c) Check in turn: $1 = 1 + 0$, $5 = 4 + 1$, $9 = 9 + 0$, $13 = 9 + 4$, $17 = 16 + 1$.
$21$: the squares below $21$ are $0, 1, 4, 9, 16$, and $21 - 0 = 21$, $21 - 1 = 20$, $21 - 4 = 17$, $21 - 9 = 12$, $21 - 16 = 5$ — none is a square.
So $21$ is the smallest. It is a counter-example, which shows the statement is false.