Year 2 Pure · Chapter 1

Proof

Specification: Edexcel Pure 1.1 — Proof · AQA section A1

Download chapter PDF Scroll this chapter

In this chapter

1. What counts as a proof
2. Proof by deduction
3. Exhaustion and counter-examples
4. Proof by contradiction
Practice

Key facts — this chapter

A proof is a chain of correct steps from facts you know to the statement, and it must cover every case. Checking examples is not a proof.
Deduction: write the numbers algebraically ( $2n$ for even, $2n + 1$ for odd) and argue from the definitions.
Exhaustion: split into a finite set of cases that covers everything, and prove each one.
Counter-example: a single case where a statement fails disproves it.
Contradiction: assume the statement is false, reason correctly, and reach something impossible. The assumption must be wrong, so the statement is true.
The two classics: $\sqrt{2}$ is irrational, and there are infinitely many primes.

In Year 1, proof turned up inside “show that” questions: expand, simplify, and arrive at what you were told. Year 2 adds one new method, proof by contradiction. It proves things that no amount of checking could ever settle, like the fact that the primes never run out.

1. What counts as a proof

A proof has to work for every case the statement covers, and there are usually infinitely many. So instead of numbers, you use letters that could stand for any of them.

Writing numbers algebraically

For an integer $n$ :

an even number is $2n$ , and an odd number is $2n + 1$ ;
consecutive integers are $n$ , $n + 1$ , $n + 2$ , …;
a multiple of $k$ is $kn$ ;
a rational number is $\dfrac{a}{b}$ , where $a$ and $b$ are integers and $b \neq 0$ . You can always take the fraction in its lowest terms, so $a$ and $b$ have no common factor.

Proofs also use a little notation, which exam questions expect you to read and write:

Symbol	Meaning
$\Rightarrow$	implies: if the left is true, so is the right
$\Leftrightarrow$	if and only if: each side implies the other
$\in$	is a member of, as in $n \in \mathbb{Z}$
$\mathbb{N}$ , $\mathbb{Z}$ , $\mathbb{Q}$ , $\mathbb{R}$	the natural numbers $1, 2, 3, \dots$ , the integers, the rational numbers, the real numbers

Common mistake

Two odd numbers are $2m + 1$ and $2n + 1$ , not $2n + 1$ twice. Using the same letter makes them the same number, so your proof only covers one odd number added to itself.

2. Proof by deduction

Start from what you know, write it algebraically, and let the algebra show the result. The last line should make the property visible: a factor of $3$ outside a bracket, or a square that can’t be negative.

Worked example 1.1 · Consecutive odd numbers

Prove that the difference between the squares of two consecutive odd numbers is always a multiple of $8$ .

Two consecutive odd numbers are $2n + 1$ and $2n + 3$ , for an integer $n$ .
Expand both squares:
$\begin{gathered} (2n + 3)^2 = 4n^2 + 12n + 9 \\ (2n + 1)^2 = 4n^2 + 4n + 1 \end{gathered}$
Subtract: the difference is $8n + 8 = 8(n + 1)$ , and $n + 1$ is an integer, so the difference is a multiple of $8$ .

Worked example 1.2 · An inequality

Prove that $x^2 - 6x + 10 > 0$ for all real values of $x$ .

Complete the square:
$x^2 - 6x + 10 = (x - 3)^2 + 1$
A square is never negative, so $(x - 3)^2 \geq 0$ for every real $x$ .
So $(x - 3)^2 + 1 \geq 1 > 0$ , which is what we wanted.

3. Exhaustion and counter-examples

Proof by exhaustion splits the statement into cases that between them cover everything, then proves each one. For integers, even and odd is the usual split. For remainders on division by $3$ , the cases are $3k$ , $3k + 1$ and $3k + 2$ .

Worked example 1.3 · Square numbers

Prove that every square number is either a multiple of $4$ or one more than a multiple of $4$ .

Every integer $n$ is even or odd, so there are two cases.

$n$ even, $n = 2k$ :
$n^2 = 4k^2$
which is a multiple of $4$ .
$n$ odd, $n = 2k + 1$ :
$\begin{aligned} n^2 &= 4k^2 + 4k + 1 \\ &= 4(k^2 + k) + 1 \end{aligned}$
which is one more than a multiple of $4$ .

The two cases cover every integer, so the statement is true.

A counter-example works the other way. A statement about every case is false as soon as one case fails, and that one case is all the disproof needs.

Worked example 1.4 · Forty successes, then a failure

Disprove the statement: ” $n^2 + n + 41$ is prime for every positive integer $n$ .”

Take $n = 40$ :

\begin{aligned} 40^2 + 40 + 41 &= 1600 + 40 + 41 \\ &= 1681 = 41^2 \end{aligned}

$1681$ is not prime, so the statement is false.

Values of n squared plus n plus 41 for n from 0 to 45, plotted as dots: every one is prime up to n = 39, and several are not prime from n = 40 on — n² + n + 41 is prime for n = 0, 1, …, 39, then fails at n = 40.

Why it works

Checking cases can build confidence, but it can’t prove anything about infinitely many numbers. The polynomial $n^2 + n + 41$ gives primes for the first forty values of $n$ , so a checker would stop long before it fails. Only an argument that covers every $n$ at once counts as a proof.

4. Proof by contradiction

Some statements can’t be reached by deduction: ” $\sqrt{2}$ is irrational” says what a number is not. For those, you argue backwards.

Proof by contradiction

Assume the statement is false: assume its opposite.
Reason correctly from that assumption.
Reach a contradiction: something that can’t be true, such as a clash with the assumption itself or with a known fact.
Conclude that the assumption was false, so the statement is true.

Why it works

Correct reasoning never leads from a true starting point to a false conclusion. So if careful steps end somewhere impossible, the starting point must have been false. The starting point was “the statement is false”, so the statement is true.

The first step is to write down the opposite exactly:

Statement	Assume instead
$\sqrt{2}$ is irrational	$\sqrt{2} = \dfrac{a}{b}$ , with integers $a$ , $b$ that have no common factor
There are infinitely many primes	There are finitely many primes
If $n^2$ is even, then $n$ is even	$n^2$ is even and $n$ is odd
There are no integers with property P	There is an integer with property P

Worked example 1.5 · Even squares come from even numbers

Prove that for any integer $n$ , if $n^2$ is even then $n$ is even.

Assume the opposite: $n^2$ is even and $n$ is odd.
$n$ is odd, so $n = 2k + 1$ for some integer $k$ , and
$\begin{aligned} n^2 &= 4k^2 + 4k + 1 \\ &= 2(2k^2 + 2k) + 1 \end{aligned}$
That makes $n^2$ odd, which contradicts $n^2$ being even.
So the assumption is false: if $n^2$ is even, $n$ is even.

Worked example 1.6 · The square root of 2 is irrational

Prove by contradiction that $\sqrt{2}$ is irrational.

Assume $\sqrt{2}$ is rational: $\sqrt{2} = \dfrac{a}{b}$ , where $a$ and $b$ are integers with no common factor and $b \neq 0$ .
Square both sides and rearrange:
$2 = \frac{a^2}{b^2} \quad\Rightarrow\quad a^2 = 2b^2$
So $a^2$ is even, and by Example 1.5, $a$ is even.
Write $a = 2k$ . Then
$4k^2 = 2b^2 \quad\Rightarrow\quad b^2 = 2k^2$
So $b^2$ is even, and $b$ is even too.
Now $a$ and $b$ are both even, so they share the factor $2$ . That contradicts “no common factor”, so $\sqrt{2}$ is irrational.

Common mistake

Don’t stop at the contradiction. Say what it contradicts and what that proves: “This contradicts $a$ and $b$ having no common factor, so $\sqrt{2}$ is irrational.” Mark schemes award a mark for that closing sentence.

Worked example 1.7 · There are infinitely many primes

Prove by contradiction that there are infinitely many prime numbers.

Assume there are finitely many primes, and list them all: $p_1, p_2, \dots, p_n$ .
Multiply them together and add $1$ :
$N = p_1 p_2 \cdots p_n + 1$
$N > 1$ , so $N$ has at least one prime factor. Every prime is on the list, so that factor is one of $p_1, \dots, p_n$ .
But dividing $N$ by any $p_i$ leaves remainder $1$ , so no prime on the list divides $N$ .
That’s a contradiction, so the list can’t be complete. There are infinitely many primes.

Common mistake

The proof does not say that $N$ itself is prime. Often it isn’t: $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30\,031 = 59 \times 509$ . What the proof needs is a prime factor that is missing from the list, and $59$ and $509$ are both missing.

Pretend the primes you pick are all the primes there are. Multiply them, add 1, and factorise the result: every prime factor it has is one your list is missing.

Your list

Divide N by each prime on the list

The prime factors of N

Practice

Twelve questions in three tiers. Try each one properly before opening the solution — the solutions show full method, not just answers.

Warm-up

1 [2 marks]

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

Show solution

Let the two odd numbers be $2m + 1$ and $2n + 1$ , where $m$ and $n$ are integers. Then

\begin{aligned} (2m + 1) + (2n + 1) &= 2m + 2n + 2 \\ &= 2(m + n + 1) \end{aligned}

$m + n + 1$ is an integer, so the sum is even.

2 [3 marks]

Find a counter-example to each statement.

For all real $x$ , $x^2 \geq x$ . [1]
If $n$ is prime, then $2^n - 1$ is prime. [2]

Show solution

(a) Take $x = \tfrac{1}{2}$ : $x^2 = \tfrac{1}{4}$ , which is less than $\tfrac{1}{2}$ .

(b) Try the primes in order. $n = 2, 3, 5, 7$ give $3, 7, 31, 127$ , which are all prime, but $n = 11$ gives

2^{11} - 1 = 2047 = 23 \times 89

which is not prime.

3 [3 marks]

Write down the assumption you would start from to prove each statement by contradiction.

$\sqrt{5}$ is irrational.
There is no largest even number.
If $n^3$ is odd, then $n$ is odd.

Show solution

(a) Assume $\sqrt{5} = \dfrac{a}{b}$ , where $a$ and $b$ are integers with no common factor and $b \neq 0$ .

(b) Assume there is a largest even number, $N$ .

(c) Assume $n^3$ is odd and $n$ is even.

4 [3 marks]

Prove by exhaustion that no square number ends in the digit $7$ .

Show solution

Write $n = 10k + d$ , where $d$ is the last digit of $n$ . Then

\begin{aligned} n^2 &= 100k^2 + 20kd + d^2 \\ &= 10(10k^2 + 2kd) + d^2 \end{aligned}

so $n^2$ ends in the same digit as $d^2$ . Check all ten possible last digits: $0^2 = 0$ , $1^2 = 1$ , $2^2 = 4$ , $3^2 = 9$ , $4^2 = 16$ , $5^2 = 25$ , $6^2 = 36$ , $7^2 = 49$ , $8^2 = 64$ and $9^2 = 81$ .

So $n^2$ ends in $0, 1, 4, 5, 6$ or $9$ . None of these is $7$ , so no square number ends in $7$ .

Standard

5 [3 marks]

Prove that $(n + 3)^2 - n^2$ is odd for every integer $n$ .

Show solution

\begin{aligned} (n + 3)^2 - n^2 &= n^2 + 6n + 9 - n^2 \\ &= 6n + 9 \\ &= 2(3n + 4) + 1 \end{aligned}

$3n + 4$ is an integer, so this is one more than an even number: it is odd.

6 [4 marks]

Prove that for all positive real numbers $a$ and $b$ ,

\frac{a + b}{2} \geq \sqrt{ab}

Show solution

$a$ and $b$ are positive, so $\sqrt{a}$ and $\sqrt{b}$ are real. A square is never negative, so

\left(\sqrt{a} - \sqrt{b}\right)^2 \geq 0

Expanding, $a - 2\sqrt{ab} + b \geq 0$ , so $a + b \geq 2\sqrt{ab}$ . Divide by $2$ :

\frac{a + b}{2} \geq \sqrt{ab}

7 [4 marks]

Prove that for any integer $n$ , if $n^2$ is a multiple of $3$ then $n$ is a multiple of $3$ .

Show solution

Assume the opposite: $n^2$ is a multiple of $3$ and $n$ is not. Then $n$ leaves remainder $1$ or $2$ on division by $3$ , so there are two cases.

$n = 3k + 1$ :

\begin{aligned} n^2 &= 9k^2 + 6k + 1 \\ &= 3(3k^2 + 2k) + 1 \end{aligned}

$n = 3k + 2$ :

\begin{aligned} n^2 &= 9k^2 + 12k + 4 \\ &= 3(3k^2 + 4k + 1) + 1 \end{aligned}

In both cases $n^2$ is one more than a multiple of $3$ , so it is not a multiple of $3$ . This contradicts the assumption, so if $n^2$ is a multiple of $3$ , then $n$ is a multiple of $3$ .

8 [4 marks]

Prove by contradiction that there are no positive integers $x$ and $y$ such that $x^2 - y^2 = 1$ .

Show solution

Assume there are positive integers $x$ and $y$ with $x^2 - y^2 = 1$ . Factorise:

(x - y)(x + y) = 1

$x$ and $y$ are at least $1$ , so $x + y \geq 2$ . Then

x - y = \frac{1}{x + y}

lies strictly between $0$ and $1$ , so it is not an integer. But $x - y$ is a difference of integers, so it is an integer. This contradiction shows there are no such positive integers.

9 [4 marks]

Prove by contradiction that if $a$ is rational and $b$ is irrational, then $a + b$ is irrational.

Show solution

Assume $a + b$ is rational. Write $a + b = \dfrac{p}{q}$ and $a = \dfrac{m}{n}$ , where $p$ , $q$ , $m$ and $n$ are integers and $q, n \neq 0$ . Then

b = \frac{p}{q} - \frac{m}{n} = \frac{pn - mq}{qn}

$pn - mq$ and $qn$ are integers, and $qn \neq 0$ , so $b$ is rational. This contradicts $b$ being irrational, so $a + b$ is irrational.

Exam style

10 [5 marks]

Prove by contradiction that $\sqrt{3}$ is irrational. You may use the result of Question 7.

Show solution

Assume $\sqrt{3}$ is rational: $\sqrt{3} = \dfrac{a}{b}$ , where $a$ and $b$ are integers with no common factor and $b \neq 0$ . Square and rearrange:

3 = \frac{a^2}{b^2} \quad\Rightarrow\quad a^2 = 3b^2

So $a^2$ is a multiple of $3$ , and by Question 7 so is $a$ . Write $a = 3k$ :

9k^2 = 3b^2 \quad\Rightarrow\quad b^2 = 3k^2

So $b^2$ is a multiple of $3$ , and so is $b$ . Then $a$ and $b$ share the factor $3$ , which contradicts their having no common factor. So $\sqrt{3}$ is irrational.

11 [5 marks]

Prove by contradiction that $\log_2 3$ is irrational.

Show solution

Assume $\log_2 3$ is rational. It is positive, because $3 > 1$ , so we can write $\log_2 3 = \dfrac{a}{b}$ with $a$ and $b$ positive integers. Then

2^{a/b} = 3 \quad\Rightarrow\quad 2^a = 3^b

$a \geq 1$ , so $2^a$ is even. But $3^b$ is a product of odd numbers, so it is odd. An even number can’t equal an odd number, so this is a contradiction, and $\log_2 3$ is irrational.

12 [6 marks]

Show that $2 \times 3 \times 5 \times 7 + 1$ is prime. [2]
It is given that $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 59 \times 509$ . A student says this shows that the proof that there are infinitely many primes is wrong. Explain why the student is mistaken. [2]
Prove that for any list of primes $p_1, p_2, \dots, p_n$ , the number $p_1 p_2 \cdots p_n + 1$ is not divisible by any prime in the list. [2]

Show solution

(a) $2 \times 3 \times 5 \times 7 + 1 = 211$ . If $211$ were not prime, it would have a prime factor no bigger than $\sqrt{211}$ , which is less than $15$ . So it is enough to check $2, 3, 5, 7, 11, 13$ . Each of $2, 3, 5, 7$ leaves remainder $1$ , and $211 = 11 \times 19 + 2 = 13 \times 16 + 3$ . None divides $211$ , so $211$ is prime.

(b) The proof never claims that $p_1 p_2 \cdots p_n + 1$ is prime. It shows that the number has a prime factor missing from the list. Here the prime factors are $59$ and $509$ , and neither is $2, 3, 5, 7, 11$ or $13$ , which is exactly what the proof says.

(c) $p_1 p_2 \cdots p_n$ is a multiple of each $p_i$ , so $p_1 p_2 \cdots p_n + 1$ leaves remainder $1$ on division by $p_i$ . Every prime is at least $2$ , so a remainder of $1$ is not $0$ , and $p_i$ does not divide the number.