Proof by Deduction and Exhaustion – A Level Maths Year 1

1 What Proof by Deduction Is

Proof by deduction starts from facts that are known to be true — definitions, earlier results, the laws of algebra — and moves step by logical step to the result. Because it uses general letters rather than particular numbers, it covers every case at once.

Most deduction proofs at this level fall into three families:

Type	Key idea	Example claim
Number properties	Write integers as $2n$, $2n+1$, $n$, $n+1, \dots$ and factorise the result	"The square of an odd number is odd."
Positivity	Complete the square, then use (square) $\geqslant 0$	"$x^2 + 4x + 7 > 0$ for all real $x$."
Identities	Expand and simplify one side until it matches the other	"$(x + y)^2 - (x - y)^2 \equiv 4xy$."

Representing integers ($n \in \mathbb{Z}$)

Even $= 2n$ · Odd $= 2n + 1$ · Multiple of $k$ $= kn$
Consecutive: $n,\ n+1,\ n+2$ · Consecutive even: $2n,\ 2n+2$ · Consecutive odd: $2n+1,\ 2n+3$

The target form. Before you start, decide what the last line must look like. "Even" means $2 \times (\text{integer})$; "odd" means $2 \times (\text{integer}) + 1$; "a multiple of $5$" means $5 \times (\text{integer})$. Then steer your algebra towards that form.

2 Proofs about Odd, Even and Consecutive Integers

Worked Example 1 — The square of an odd number

Prove that the square of any odd number is odd.

①Let the odd number be $2n + 1$, where $n \in \mathbb{Z}$.

②$(2n + 1)^2 = 4n^2 + 4n + 1$

③$= 2\left(2n^2 + 2n\right) + 1$

④$2n^2 + 2n$ is an integer, so this is of the form $2k + 1$ with $k \in \mathbb{Z}$.

⑤Therefore the square of any odd number is odd. $\blacksquare$

Worked Example 2 — Consecutive squares

Prove that the difference between the squares of two consecutive integers is always odd.

①Let the integers be $n$ and $n + 1$, where $n \in \mathbb{Z}$.

②$(n + 1)^2 - n^2 = n^2 + 2n + 1 - n^2 = 2n + 1$

③$2n + 1$ is odd for every integer $n$.

④Therefore the difference between the squares of two consecutive integers is odd. $\blacksquare$

Notice the bonus fact: the difference $2n + 1$ is also the sum of the two integers, $n + (n+1)$. Proofs often reveal more than they were asked for.

Worked Example 3 — Using a known fact inside a proof

Prove that the product of two consecutive even numbers is a multiple of $8$.

①Let the numbers be $2n$ and $2n + 2$, where $n \in \mathbb{Z}$.

②$2n(2n + 2) = 4n(n + 1)$

③$n$ and $n + 1$ are consecutive integers, so one of them is even. Hence $n(n+1)$ is even: $n(n+1) = 2m$ for some $m \in \mathbb{Z}$.

④So the product is $4 \times 2m = 8m$.

⑤Therefore the product of two consecutive even numbers is a multiple of $8$. $\blacksquare$

Stopping at $4n(n+1)$ only shows a multiple of $4$. The extra factor of $2$ comes from the fact about consecutive integers — and you must say why it holds.

3 Completing the Square to Prove Positivity

The key fact

For every real number $t$: $t^2 \geqslant 0$
So $a(x + p)^2 + q > 0$ for all real $x$ whenever $a > 0$ and $q > 0$

Worked Example 4 — A quadratic that is always positive

Prove that $x^2 + 4x + 7 > 0$ for all real values of $x$.

①Complete the square: $x^2 + 4x + 7 \equiv (x + 2)^2 - 4 + 7 = (x + 2)^2 + 3$.

②$(x + 2)^2 \geqslant 0$ for all real $x$.

③So $(x + 2)^2 + 3 \geqslant 3 > 0$.

④Therefore $x^2 + 4x + 7 > 0$ for all real $x$. $\blacksquare$

The proof gives more than was asked: the least value of the expression is $3$, when $x = -2$.

Worked Example 5 — A leading coefficient other than 1

Prove that $2x^2 - 4x + 5$ is positive for all real $x$.

①Factor out the $2$ from the $x$ terms: $2\left(x^2 - 2x\right) + 5$.

②$= 2\left[(x - 1)^2 - 1\right] + 5 = 2(x - 1)^2 + 3$.

③$(x-1)^2 \geqslant 0 \Rightarrow 2(x - 1)^2 \geqslant 0 \Rightarrow 2(x-1)^2 + 3 \geqslant 3 > 0$.

④Therefore $2x^2 - 4x + 5 > 0$ for all real $x$. $\blacksquare$

Worked Example 6 — An inequality in two variables

Prove that $x^2 + y^2 \geqslant 2xy$ for all real $x$ and $y$.

①Start from a fact that is certainly true: $(x - y)^2 \geqslant 0$ for all real $x, y$.

②Expand: $x^2 - 2xy + y^2 \geqslant 0$.

③Add $2xy$ to both sides: $x^2 + y^2 \geqslant 2xy$. $\blacksquare$

How did we know to start there? Do the rough work backwards — $x^2 + y^2 - 2xy \geqslant 0$ looks like $(x-y)^2$ — then write the proof forwards, starting from the true fact.

4 Proving Identities

An identity, written with $\equiv$, is true for every value of the variables. To prove one, take one side (usually the more complicated), manipulate it, and arrive at the other side. Never treat it like an equation by doing the same thing to both sides.

Worked Example 7 — Proving an identity, then using it

(a) Prove that $(x + y)^2 - (x - y)^2 \equiv 4xy$. (b) Hence show that $53^2 - 47^2 = 600$ without a calculator.

①LHS $= \left(x^2 + 2xy + y^2\right) - \left(x^2 - 2xy + y^2\right)$

②$= 4xy = $ RHS. $\blacksquare$

③(b) $x + y = 53$ and $x - y = 47$ give $x = 50$, $y = 3$.

④$53^2 - 47^2 = 4(50)(3) = 600$.

Worked Example 8 — An identity that gives a divisibility result

Prove that $n^3 - n \equiv (n - 1)n(n + 1)$, and hence that $n^3 - n$ is even for every integer $n$.

①RHS $= (n-1)(n+1) \times n = \left(n^2 - 1\right)n = n^3 - n = $ LHS. $\blacksquare$

②$(n-1)$, $n$, $(n+1)$ are three consecutive integers, so at least one of them is even.

③A product with an even factor is even, so $n^3 - n$ is even for every integer $n$. $\blacksquare$

The same argument shows $n^3 - n$ is a multiple of $3$ (one of any three consecutive integers is a multiple of $3$) — and so a multiple of $6$.

5 Proof by Exhaustion

In proof by exhaustion you split the situation into a finite number of cases that between them cover every possibility, and prove the result in each case separately. If even one case is left out, the proof fails.

Useful ways to split the integers

Two cases: $2k,\ 2k+1$ · Three cases: $3k,\ 3k+1,\ 3k+2$
Four cases: $4k,\ 4k+1,\ 4k+2,\ 4k+3$ · Six cases: $6k,\ 6k+1, \dots, 6k+5$

Worked Example 9 — Square numbers and remainders on division by 3

Prove that every square number leaves remainder $0$ or $1$ when divided by $3$.

①Every integer $n$ is of the form $3k$, $3k + 1$ or $3k + 2$ for some $k \in \mathbb{Z}$.

②$n = 3k$: $\;n^2 = 9k^2 = 3\left(3k^2\right)$, remainder $0$.

③$n = 3k + 1$: $\;n^2 = 9k^2 + 6k + 1 = 3\left(3k^2 + 2k\right) + 1$, remainder $1$.

④$n = 3k + 2$: $\;n^2 = 9k^2 + 12k + 4 = 3\left(3k^2 + 4k + 1\right) + 1$, remainder $1$.

⑤All cases are covered, so every square leaves remainder $0$ or $1$ on division by $3$. $\blacksquare$

Consequence: no square number leaves remainder $2$ on division by $3$. For example, $2\,000\,000\,000\,003$ has digit sum $5$, so it leaves remainder $2$ when divided by $3$ — it cannot be a perfect square, and no calculator is needed.

Worked Example 10 — Squares and division by 4

Prove that the square of any integer is either a multiple of $4$ or one more than a multiple of $4$.

①Case 1, $n$ even: $n = 2k$, so $n^2 = 4k^2$ — a multiple of $4$.

②Case 2, $n$ odd: $n = 2k + 1$, so $n^2 = 4k^2 + 4k + 1 = 4\left(k^2 + k\right) + 1$ — one more than a multiple of $4$.

③Every integer is even or odd, so the result holds for all integers. $\blacksquare$

Worked Example 11 — Primes greater than 3

Prove that every prime number greater than $3$ is one more or one less than a multiple of $6$.

①Every integer is of the form $6k,\ 6k+1,\ 6k+2,\ 6k+3,\ 6k+4$ or $6k+5$.

②$6k = 2(3k)$, $\;6k + 2 = 2(3k + 1)$ and $6k + 4 = 2(3k + 2)$ are even, so (being greater than $2$) not prime.

③$6k + 3 = 3(2k + 1)$ is a multiple of $3$, so (being greater than $3$) not prime.

④The only forms left are $6k + 1$ and $6k + 5 = 6(k + 1) - 1$.

⑤So every prime greater than $3$ is one more or one less than a multiple of $6$. $\blacksquare$

The converse is false. $25 = 6(4) + 1$ is of the right form but is not prime. The proof only says primes must be of this form, not that every number of this form is prime.

Worked Example 12 — Exhaustion over a small finite set

Prove that $n^2 + n + 11$ is prime for every integer $n$ with $1 \leqslant n \leqslant 6$.

$n$	1	2	3	4	5	6
$n^2 + n + 11$	13	17	23	31	41	53

①Every value is at most $53$, and $\sqrt{53} < 8$, so it is enough to check divisibility by $2, 3, 5$ and $7$. None of the six values is divisible by any of these, so each one is prime.

②Every case in the range has been checked, so the result is proved. $\blacksquare$

This is a valid proof only because the set is finite. It says nothing about $n = 11$, where $11^2 + 11 + 11 = 143 = 11 \times 13$.

6 Quick Reference

Even / odd

$2n$ and $2n+1$, $n \in \mathbb{Z}$. Use different letters for different numbers.

Consecutive

$n, n+1, n+2, \dots$ — one of any two is even.

Target form

Factorise to $k \times (\text{integer})$ or $2 \times (\text{integer}) + 1$.

Positivity

$a(x+p)^2 + q$ with $a, q > 0$ is always positive.

Squares

$t^2 \geqslant 0$ for every real $t$.

Identity

Work on one side only until it becomes the other.

Exhaustion

Finite cases that cover everything; prove each.

Remainders

Squares are $0$ or $1$ mod $3$, and $0$ or $1$ mod $4$.

Finish

End with a sentence stating the result.

7 Practice Questions

Question 1

Prove that the sum of an odd number and an even number is odd.

▶ Show solution

Let the numbers be $2m + 1$ and $2n$, with $m, n \in \mathbb{Z}$.

Sum $= 2m + 2n + 1 = 2(m + n) + 1$, and $m + n \in \mathbb{Z}$.

So the sum is of the form $2k + 1$ — it is odd.

Question 2

Prove that the sum of any five consecutive integers is a multiple of $5$.

▶ Show solution

Let the integers be $n, n+1, n+2, n+3, n+4$ with $n \in \mathbb{Z}$.

Sum $= 5n + 10 = 5(n + 2)$, and $n + 2 \in \mathbb{Z}$.

Therefore the sum is a multiple of $5$.

Question 3

Prove that $(n + 5)^2 - (n + 1)^2$ is a multiple of $8$ for every integer $n$.

▶ Show solution

$(n+5)^2 - (n+1)^2 = \left(n^2 + 10n + 25\right) - \left(n^2 + 2n + 1\right) = 8n + 24$

$= 8(n + 3)$, and $n + 3 \in \mathbb{Z}$.

Therefore the expression is a multiple of $8$ for every integer $n$.

Question 4

Prove that $x^2 - 8x + 20 > 0$ for all real $x$, and state the least value of $x^2 - 8x + 20$.

▶ Show solution

$x^2 - 8x + 20 \equiv (x - 4)^2 - 16 + 20 = (x - 4)^2 + 4$.

$(x - 4)^2 \geqslant 0$, so $(x-4)^2 + 4 \geqslant 4 > 0$ for all real $x$.

The least value is $4$, when $x = 4$.

Question 5

Prove that $3x^2 + 6x + 5 > 0$ for all real $x$.

▶ Show solution

$3x^2 + 6x + 5 = 3\left(x^2 + 2x\right) + 5 = 3\left[(x + 1)^2 - 1\right] + 5 = 3(x + 1)^2 + 2$.

$(x + 1)^2 \geqslant 0 \Rightarrow 3(x+1)^2 \geqslant 0 \Rightarrow 3(x+1)^2 + 2 \geqslant 2 > 0$.

Therefore $3x^2 + 6x + 5 > 0$ for all real $x$.

Question 6

Prove by exhaustion that $n^2 + n$ is even for every integer $n$.

▶ Show solution

Case 1: $n$ even, $n = 2k$. Then $n^2 + n = 4k^2 + 2k = 2\left(2k^2 + k\right)$ — even.

Case 2: $n$ odd, $n = 2k + 1$. Then $n^2 + n = 4k^2 + 4k + 1 + 2k + 1 = 4k^2 + 6k + 2 = 2\left(2k^2 + 3k + 1\right)$ — even.

Every integer is even or odd, so $n^2 + n$ is even for every integer $n$.

Question 7

(a) Prove that $(x + 2)^3 - x^3 \equiv 6x^2 + 12x + 8$. (b) Hence prove that the difference between the cubes of two integers that differ by $2$ is always even.

▶ Show solution

(a) $(x+2)^3 = (x+2)\left(x^2 + 4x + 4\right) = x^3 + 4x^2 + 4x + 2x^2 + 8x + 8 = x^3 + 6x^2 + 12x + 8$.

Subtracting $x^3$ gives $6x^2 + 12x + 8$, as required.

(b) Let the integers be $n$ and $n + 2$. By (a), $(n+2)^3 - n^3 = 6n^2 + 12n + 8 = 2\left(3n^2 + 6n + 4\right)$.

$3n^2 + 6n + 4$ is an integer, so the difference is even.

Question 8

Prove that $101$ is a prime number.

▶ Show solution

If $101$ had a factor other than $1$ and itself, it would have a prime factor no larger than $\sqrt{101} \approx 10.05$.

So it is enough to test the primes $2, 3, 5, 7$:

$101$ is odd; its digit sum is $2$, so not divisible by $3$; it does not end in $0$ or $5$; and $101 = 7 \times 14 + 3$.

None divides $101$, so by exhaustion $101$ is prime.

Question 9

(a) Prove that $a^2 + b^2 \geqslant 2ab$ for all real $a$ and $b$. (b) Hence prove that $x + \dfrac{1}{x} \geqslant 2$ for all $x > 0$.

▶ Show solution

(a) $(a - b)^2 \geqslant 0 \Rightarrow a^2 - 2ab + b^2 \geqslant 0 \Rightarrow a^2 + b^2 \geqslant 2ab$.

(b) For $x > 0$ we may take $a = \sqrt{x}$ and $b = \dfrac{1}{\sqrt{x}}$, both real.

Then $a^2 = x$, $b^2 = \dfrac1x$ and $ab = 1$, so (a) gives $x + \dfrac1x \geqslant 2$.

Alternative: $x + \dfrac1x - 2 = \dfrac{x^2 - 2x + 1}{x} = \dfrac{(x-1)^2}{x} \geqslant 0$ since $x > 0$.

Question 10

(a) By considering the cases $n = 3k$, $n = 3k + 1$ and $n = 3k + 2$, prove that the cube of any integer leaves remainder $0$, $1$ or $8$ when divided by $9$.

(b) Hence list the possible remainders when the sum of two cubes is divided by $9$.

▶ Show solution

(a) $n = 3k$: $\;n^3 = 27k^3 = 9\left(3k^3\right)$, remainder $0$.

$n = 3k + 1$: $\;n^3 = 27k^3 + 27k^2 + 9k + 1 = 9\left(3k^3 + 3k^2 + k\right) + 1$, remainder $1$.

$n = 3k + 2$: $\;n^3 = 27k^3 + 54k^2 + 36k + 8 = 9\left(3k^3 + 6k^2 + 4k\right) + 8$, remainder $8$.

These cases cover every integer, so the remainder is always $0$, $1$ or $8$.

(b) Adding two remainders from $\{0, 1, 8\}$: $0, 1, 8, 2, 9, 16$, which leave remainders $0, 1, 8, 2, 0, 7$ on division by $9$.

So the sum of two cubes leaves remainder $0, 1, 2, 7$ or $8$ — never $3, 4, 5$ or $6$.

(c) $2021 = 9 \times 224 + 5$, so $2021$ leaves remainder $5$ on division by $9$.

By (b) no sum of two cubes leaves remainder $5$, so $2021$ is not the sum of two cubes.

Proof by Deduction and Exhaustion · A Level Maths Year 1 · Created with MathJax