The structure of proof and proof by deduction

Highlights only0 highlighted

A proof is an argument that starts from facts you are given or already know, moves through steps that each follow from the one before, and ends at the statement you were asked to establish.

Checking a few numbers is not a proof: it only shows that the statement holds for those numbers.

This section sets out how a proof is built, then teaches the method used most often across the course, proof by deduction.

Proof is examined on both Paper 1 and Paper 2, either as a short question of its own or as the last part of a longer question, and the deduction style you learn here is the same one you use for a show-that in every other topic.

What a proof is made of

Every proof has the same three parts.

The starting point. What you are given, written in symbols. "Let $n$ be an integer" or "Given that $x > 0$ " fixes the objects the proof talks about. If the statement is about any integer, you must work with a general one, $n$ , never a particular one such as $7$ .

The chain. Each line follows from the line before it by algebra, a known result or a definition. The symbol $\Rightarrow$ ("implies") links a line to the next one; $\Leftrightarrow$ means each line implies the other. Write words where they help: "so", "since", "which is even because".

The conclusion. A sentence that states the result in the question's words: "so the sum of any four consecutive integers is never a multiple of 4". On 9MA0 papers the closing statement is a mark of its own, and it is the mark lost most often.

Writing numbers in general form

Most deduction proofs about integers rely on writing a number in a form that shows its property.

Number

General form ( $n \in \mathbb{Z}$ )

any even number

$2n$

any odd number

$2n + 1$ (or $2n - 1$ )

a multiple of $k$

$kn$

two consecutive integers

$n$ and $n + 1$

two consecutive odd numbers

$2n + 1$ and $2n + 3$

any two odd numbers (not necessarily consecutive)

$2m + 1$ and $2n + 1$

The last row matters.

If two odd numbers are unrelated, they need different letters: writing both as $2n + 1$ makes them the same number, and the proof then covers only that special case.

To show a number is a multiple of $k$ , factorise $k$ out of the whole expression and say that the bracket is an integer.

Proof by deduction

In a proof by deduction you start from what is known and reason forwards.

You need to know that this is the most commonly used method of proof throughout the course.

The two examples you need to recognise are:

using completion of the square to prove that a quadratic is positive for all values of the variable, for example that $n^2 - 6n + 10$ is positive for all values of $n$ , since $n^2 - 6n + 10 = (n - 3)^2 + 1$ and a square is never negative;

differentiation from first principles for small positive integer powers of $x$ , where the gradient of a chord is simplified and the limit taken. That proof is taught in full in the differentiation unit; it is a deduction because every line follows from the definition of the derivative.

The completing-the-square idea works because of one fact about real numbers: a square is never negative.

For every real $t$ , $t^2 \ge 0$ , with $t^2 = 0$ only when $t = 0$ .

So if you can write an expression as (a square) $+$ (a positive number), it is positive for every real value.

Write the square as $\ge 0$ , never " $> 0$ ": $(x - 5)^2$ is zero when $x = 5$ .

The sketch below shows what the algebra says for $x^2 - 10x + 27 = (x - 5)^2 + 2$ : the lowest point of the curve is $(5, 2)$ , so the curve never reaches the $x$ -axis.

The parabola y = x² − 10x + 27 opening upwards, symmetrical about the dashed line x = 5. Its lowest point is (5, 2), two units above the x-axis, so the whole curve lies above the x-axis and the curve never meets it.

Deduction with inequalities

The same forward reasoning works with inequalities, with one rule that catches people out.

Adding or subtracting the same quantity, or multiplying or dividing by a positive quantity, keeps the inequality sign.

Multiplying or dividing by a negative quantity reverses it: $-2 < 3$ , but multiplying by $-1$ gives $2 > -3$ .

When you divide by a letter, you must know its sign, and you must say in the proof where the sign reverses and why.

A line such as "dividing by $2a$ , which is negative since $a < 0$ , reverses the inequality" earns the reasoning mark.

Why it works (not examined): a proof is permanent

A statement checked for many values could still fail at the next one.

Pierre de Fermat believed that every number of the form $2^{2^n} + 1$ is prime.

The first five, $3, 5, 17, 257$ and $65\,537$ , are prime, but Leonhard Euler later showed that the next one, $2^{32} + 1 = 4\,294\,967\,297$ , equals $641 \times 6\,700\,417$ .

A deduction from a general $n$ covers every case at once, which is why it is the standard of evidence in mathematics.

Key terms

Proof: a logical argument that proceeds from given assumptions through a series of logical steps to a conclusion.

Proof by deduction: a proof that starts from known facts or definitions and reasons forwards, each step following from the previous one, until the required statement is reached.

Implies ( $\Rightarrow$ ): $p \Rightarrow q$ means that if $p$ is true then $q$ is true.

If and only if ( $\Leftrightarrow$ ): $p \Leftrightarrow q$ means $p \Rightarrow q$ and $q \Rightarrow p$ .

Integers: the set $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$ ; $n \in \mathbb{Z}$ means $n$ is an integer.

How the marks work

Every mark is worth one. M1 is for a correct method applied to this problem: a formula quoted and then used with your values keeps the M even after a slip.

A1 is for an accurate answer or line and needs the M before it. B1 is an independent mark: a value, a feature of a sketch, a reason, a statement or a piece of notation.

dM1 depends on the M mark before it, and ddM1 on the two before it. A1* is the last mark of a "show that" or a proof: earned only with no errors, the printed result written out in full and, for a proof, the closing statement.

cso means correct solution only; ft means a wrong earlier value carried forward correctly still earns marks; oe means any equivalent form; awrt means "answers which round to"; isw means ignore subsequent working. A special case (SC) gives partial credit for a recognised wrong route.

Under the calculator banner ("In this question you must show all stages of your working. Solutions relying entirely on calculator technology are not acceptable.") or a named method such as "using algebra", a correct answer with no working, or an argument in words where algebra was asked for, scores 0 or a special case.

Elsewhere on the pure papers, write the method anyway: a wrong answer on its own scores nothing, but a correct method with a slip keeps its M marks.

On the Statistics part of Paper 3 a bare correct answer usually scores full marks unless the part says "show" or asks for working, but the distribution written before the number is often a mark of its own.

If you make two attempts and cross neither out, the examiner marks the most complete final answer, which may not be the one you want: cross out the other.

Worked example 1: four consecutive integers

Prove that the sum of any four consecutive integers is never a multiple of 4.

(3)

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

B1 (a general set of four consecutive integers)

$n + (n + 1) + (n + 2) + (n + 3) = 4n + 6 = 4(n + 1) + 2$ M1 (sum written as a multiple of 4 plus a remainder)

$4(n + 1)$ is a multiple of 4, so the sum leaves remainder 2 when divided by 4.

Hence the sum of any four consecutive integers is never a multiple of 4.

A1* (reason and closing statement)

Answer: the sum is always 2 more than a multiple of 4.

A candidate who stops at " $4n + 6$ " without explaining why it is not a multiple of 4 scores B1 M1 A0: " $4n + 6$ is not divisible by 4" needs the reason, the remainder of 2.

Worked example 2: positive for all values, by completing the square

(a) Express $x^2 - 10x + 27$ in the form $(x + p)^2 + q$ , where $p$ and $q$ are constants to be found. (2)

(b) Hence prove that $x^2 - 10x + 27 > 0$ for all real values of $x$ . (2)

(a) $x^2 - 10x + 27 = (x - 5)^2 - 25 + 27$ M1 (half the coefficient of $x$ , and its square subtracted)

$= (x - 5)^2 + 2$ , so $p = -5$ , $q = 2$ A1

(b) $(x - 5)^2 \ge 0$ for all real $x$ M1 (the square stated to be non-negative, with $\ge$ )

so $(x - 5)^2 + 2 \ge 2 > 0$ .

Hence $x^2 - 10x + 27 > 0$ for all real values of $x$ .

A1* (closing statement)

Answer: the least value of the expression is $2$ , at $x = 5$ , which is the turning point in the sketch above.

Writing " $(x - 5)^2 > 0$ " is false at $x = 5$ and loses the A1*; "squares are always positive" is not accepted either.

Worked example 3: dividing by a negative

Given that $a$ and $b$ are real numbers such that

$a < 0$

$(a + b)^2 < a^2 + b^2 + 4a$

show that $b > 2$ .

(2)

$a^2 + 2ab + b^2 < a^2 + b^2 + 4a \Rightarrow 2ab < 4a$ M1 (expanded and simplified correctly)

Dividing both sides by $2a$ , which is negative because $a < 0$ , reverses the inequality: $b > 2$ A1* (the reversal stated with its reason)

Answer: $b > 2$ .

A candidate who writes $b < 2$ from dividing, then "so $b > 2$ " to match the printed answer, scores M1 A0: the printed answer must follow from your lines, not be written after them.

Worked example 4: an inequality between two means

Prove that for all positive real numbers $x$ and $y$ ,

\frac{x + y}{2} \ge \sqrt{xy}. \quad (3)

Plan: a square is never negative, and since $x$ and $y$ are positive, $\sqrt{x}$ and $\sqrt{y}$ are real.

Start from the square of their difference.

$\left(\sqrt{x} - \sqrt{y}\right)^2 \ge 0$ for all positive $x$ and $y$ B1 (a true starting statement)

$\Rightarrow x - 2\sqrt{x}\sqrt{y} + y \ge 0 \Rightarrow x + y \ge 2\sqrt{xy}$ M1 (expanded, using $(\sqrt{x})^2 = x$ and $\sqrt{x}\sqrt{y} = \sqrt{xy}$ )

Dividing by 2 (positive, so the sign is kept): $\dfrac{x + y}{2} \ge \sqrt{xy}$ for all positive $x$ and $y$ .

A1*

Answer: the mean of two positive numbers is at least the square root of their product, with equality only when $x = y$ .

Notice the direction of the argument: a proof that starts from the printed inequality and works down to " $(\sqrt{x} - \sqrt{y})^2 \ge 0$ " has the logic back to front.

If you find the idea that way in rough, write the final proof starting from the true statement.

Worked example 5: consecutive odd squares (single-part, plan first)

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

(3)

Plan: write two consecutive odd numbers with one letter, expand both squares, subtract, and take out a factor of 8.

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

$(2n + 3)^2 - (2n + 1)^2 = (4n^2 + 12n + 9) - (4n^2 + 4n + 1) = 8n + 8$ M1 (both squares expanded, three terms each)

$= 8(n + 1)$ , and $n + 1$ is an integer, so the difference is a multiple of 8.

A1*

Answer: the difference is $8(n + 1)$ .

Here one letter is right, because consecutive odd numbers are linked.

For two odd numbers that are not linked you would need $2m + 1$ and $2n + 1$ .

Exam tip

Finish every proof with a sentence that repeats the statement you were asked to prove, in the question's own words ("so ...

is a multiple of 8 for all integers $n$ ").

The examiners give this closing statement its own mark, and it is the mark that candidates lose most often on proof questions, even after correct algebra.

Common mistakes

Checking examples instead of proving. Substituting $n = 1, 2, 3$ shows nothing about $n = 4$ . It is tempting because it feels convincing; use a general letter instead.

The same letter for unrelated numbers. "Let the odd numbers be $2n + 1$ and $2n + 1$ " proves the result only when the numbers are equal. Use $2m + 1$ and $2n + 1$ .

" $> 0$ " for a square. $(x - a)^2$ can be zero, so write $(x - a)^2 \ge 0$ . The strict sign looks harmless, but it is false at $x = a$ .

A reversal hidden or missed. When you divide by a quantity that is negative, the inequality reverses, and you must say so where it happens. Writing the right final sign without the reason loses the last mark.

No closing statement. A proof that stops at " $= 8(n + 1)$ " is unfinished. Say what the line shows.

Check your understanding

1. Prove, using algebra, that the sum of any three consecutive even numbers is a multiple of 6. (3) Total [3]

2. (a) Express $x^2 + 8x + 21$ in the form $(x + p)^2 + q$ , where $p$ and $q$ are constants to be found. (2)
(b) Hence prove that $x^2 + 8x + 21 > 0$ for all real values of $x$ . (2)
(c) Write down the minimum value of $x^2 + 8x + 21$ . (1) Total [5]

3. A student wants to prove that $n^2 + n + 41$ is a prime number for every positive integer $n$ . The student works out the value for $n = 1, 2, 3, 4$ and $5$ , finds that each is prime, and writes "so the statement is proved".
(a) Give a reason why the student's argument is not a proof. (1)
(b) Show that the statement is not true when $n = 40$ . (2) Total [3]

4. Given that $x$ and $y$ are real numbers such that

$y < 0$
$(x + y)^2 < x^2 + y^2 - 10y$

show that $x > -5$ .

(2) Total [2]

5. (a) Prove that $a^2 + b^2 \ge 2ab$ for all real numbers $a$ and $b$ . (2)
(b) Hence prove that $x + \dfrac{1}{x} \ge 2$ for all positive real numbers $x$ . (2) Total [4]

6. Prove that, for all integers $n$ , $(n + 5)^2 - (n - 1)^2$ is a multiple of 12. (3) Total [3]

Answers

1. Let the numbers be $2n$ , $2n + 2$ and $2n + 4$ , where $n \in \mathbb{Z}$ B1; sum $= 6n + 6$ M1; $= 6(n + 1)$ , and $n + 1$ is an integer, so the sum is a multiple of 6 A1* (closing statement needed). An argument in words only ("even plus even is even ...") ignores "using algebra" and scores at most a special case.

2. (a) $(x + 4)^2 - 16 + 21$ M1; $= (x + 4)^2 + 5$ , $p = 4$ , $q = 5$ A1
(b) $(x + 4)^2 \ge 0$ for all real $x$ M1; so $(x + 4)^2 + 5 \ge 5 > 0$ , hence $x^2 + 8x + 21 > 0$ for all real $x$ A1* (" $(x + 4)^2 > 0$ " loses this mark)
(c) $5$ B1ft (their $q$ )

3. (a) Checking particular values does not show that the statement holds for every positive integer $n$ B1
(b) $40^2 + 40 + 41 = 1681$ M1; $1681 = 41 \times 41$ , so it is not prime and the statement is not true A1 (the factorisation and the conclusion are both needed)

4. $x^2 + 2xy + y^2 < x^2 + y^2 - 10y \Rightarrow 2xy < -10y$ M1; dividing by $2y$ , which is negative since $y < 0$ , reverses the inequality, so $x > -5$ A1* (the reversal and its reason must be stated)

5. (a) $(a - b)^2 \ge 0$ for all real $a$ , $b$ M1; $\Rightarrow a^2 - 2ab + b^2 \ge 0 \Rightarrow a^2 + b^2 \ge 2ab$ A1*
(b) Let $a = \sqrt{x}$ and $b = \dfrac{1}{\sqrt{x}}$ , real since $x > 0$ M1; then $x + \dfrac{1}{x} \ge 2\sqrt{x} \times \dfrac{1}{\sqrt{x}} = 2$ A1* (Allow a direct proof from $\left(\sqrt{x} - \frac{1}{\sqrt{x}}\right)^2 \ge 0$ or from $(x - 1)^2 \ge 0$ divided by $x > 0$ , with the sign of $x$ stated.)

6. $(n^2 + 10n + 25) - (n^2 - 2n + 1)$ M1; $= 12n + 24$ A1; $= 12(n + 2)$ , and $n + 2$ is an integer, so it is a multiple of 12 for all integers $n$ A1*

The structure of proof and proof by deduction

Your course level