The structure of a proof: from assumptions to a conclusion

Highlights only0 highlighted

Proof is examined on Pure Mathematics P2 (WMA12/01), the second AS pure paper, and a proof question has appeared on each of the three recent P2 papers studied for these notes.

Together with the factor and remainder theorems, this unit carried 13 or 14 of the 75 marks on each of them.

P2 assumes everything in P1, so expanding brackets, factorising, completing the square and the discriminant all earn marks inside a proof.

The idea: why checking examples is not enough

Here is a pattern to explore.

Mark some points on a circle and join every pair with a straight line, placing the points so that no three lines meet at one point inside.

Count the regions the circle is cut into.

Points on the circle

Regions

Five results in a row fit "the number of regions doubles each time", and it is very tempting to predict 32 for six points.

The true count is 31.

No number of agreeing examples can show that a statement holds for every case, because the next case might be the one that breaks it.

A proof is an argument that settles every case at once.

You need to "understand and use the structure of mathematical proof, proceeding from given assumptions through a series of logical steps to a conclusion".

So a proof has three parts:

1. Given assumptions: what you are told, or may take as known (" $n$ is an odd integer", " $x$ and $y$ are positive").

2. A series of logical steps: each line follows from the lines before it, by algebra or by a fact you state.

3. A conclusion: a sentence saying that the statement you set out to prove is true.

A letter for a general number

The step that turns examples into a proof is using a letter for a general number.

Checking $3 + 5 = 8$ shows that one sum of two odd numbers is even.

Writing two odd numbers as $2a + 1$ and $2b + 1$ , where $a$ and $b$ are integers, covers every pair at once:

(2a + 1) + (2b + 1) = 2a + 2b + 2 = 2(a + b + 1),

and $a + b + 1$ is an integer, so the sum is a multiple of 2.

That last clause matters: "2 times something" is even only when the something is an integer.

Kind of number

General form ( $k$ , $a$ , $b$ integers)

Why

even

$2k$

a multiple of 2

odd

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

one more than an even number

two odd numbers that need not be equal

$2a + 1$ and $2b + 1$

separate letters, so the two are independent

consecutive integers

$n$ , $n + 1$ , $n + 2$

each is one more than the last

consecutive odd numbers

$2k + 1$ , $2k + 3$

odd numbers go up in 2s

multiple of 3

$3k$

every integer is $3k$ , $3k + 1$ or $3k + 2$

Two choices go wrong often enough to need a warning.

Writing an odd number as $4k + 1$ is tempting, because $4k + 1$ is odd for every $k$ .

But it only produces $\ldots, -3, 1, 5, 9, 13, \ldots$ and never 3 or 7, so a proof that starts there covers only half of the odd numbers.

And writing " $n = 2n + 1$ " uses one letter for two different things: it is an equation whose only solution is $n = -1$ , not a general odd number.

Implication: each line must follow from the one before

Most statements to prove have the shape "if (assumption) then (conclusion)".

The symbol $\Rightarrow$ means "implies": $A \Rightarrow B$ says that whenever $A$ is true, $B$ is true.

The arrow does not automatically run backwards.

" $x = 3 \Rightarrow x^2 = 9$ " is true, but " $x^2 = 9 \Rightarrow x = 3$ " is false, because $x$ could be $-3$ .

When both directions hold, the symbol is $\Leftrightarrow$ , read "if and only if".

This is why a proof starts from what is given and works towards what is wanted.

Starting from the statement you want and arriving at something true proves nothing, unless every step can be reversed: from $x = -3$ you can reach the true line $x^2 = 9$ , but that does not make $x = 3$ false.

Deductive proofs are examined too

The proof topic names two methods, proof by exhaustion and disproof by counter example, and each has its own section later in this unit.

Recent P2 papers have also set direct (deductive) proofs: a property of odd numbers proved from $2k + 1$ , and an inequality proved from a given condition about positive numbers.

These come under the first line of the proof topic, the structure of proof, so treat them as examined.

This section covers proofs about integers; the next covers inequalities.

Where this leads

The habits in this section, a general form, a reason for every step and a closing sentence, are used in every later proof in the course.

P4 adds proof by contradiction, which starts by assuming the statement is false.

Further Pure Mathematics adds proof by induction, which proves a statement for every positive integer $n$ by a chain of implications from one case to the next.

Outside mathematics, the same structure is used to check that a computer program always gives the right output, where testing a few inputs is no more a proof than checking a few numbers.

Detailed reasoning: what a P2 proof needs

Some P2 proof questions print In this question you must show detailed reasoning. Under that line, and in every Prove question:

Start from a general form ( $2k + 1$ , $3k + 1$ , positive $x$ and $y$ ), never from numbers. Substituting values scores nothing in a general proof.

Give the reason for each step that is not plain algebra: " $k(k + 1)$ is a product of consecutive integers, so it is even"; "dividing by $xy$ , which is positive".

End with an overall conclusion that repeats the statement. That final sentence is itself a marked step.

How the marks work

M1: a correct method applied to this question, with your values in. dM1 needs the M mark before it; ddM1 needs the two M marks before it.

A1: a correct answer or line, which needs its M mark. A1* is the last mark of a "show that" or a proof: the printed result or conclusion, reached with no errors and an intermediate line. A1cso: correct solution only.

B1: an independent mark for a correct value, fact or statement; dB1 needs the B mark before it. ft (follow through): credit for using your own earlier wrong value correctly.

awrt: any answer which rounds to the value given. isw: ignore subsequent working, so a correct answer followed by a harmless extra line keeps its marks.

Misread: copy a number wrongly and keep the character of the question, and you lose two of the A or B marks in that part, not everything.

A correct answer with no working may score nothing, above all where the calculator note is printed.

Key terms

Structure of mathematical proof: proceeding from given assumptions through a series of logical steps to a conclusion.

Integer: a whole number: positive, negative or zero.

Even, odd: an integer is even if it can be written $2k$ , and odd if it can be written $2k + 1$ , for some integer $k$ .

Implies ( $\Rightarrow$ ): $A \Rightarrow B$ means that if $A$ is true then $B$ is true. $A \Leftrightarrow B$ means each implies the other.

Worked example 1: three consecutive integers

Prove that the sum of any three consecutive integers is a multiple of 3.

(3)

1. Let the integers be $n$ , $n + 1$ and $n + 2$ , where $n$ is an integer B1 (general form, not numbers)

2. Sum $= n + (n + 1) + (n + 2) = 3n + 3$ M1

3. $= 3(n + 1)$ , and $n + 1$ is an integer, so the sum of any three consecutive integers is a multiple of 3 A1* (reason and conclusion)

Answer: the sum is $3(n + 1)$ .

The proof also says more than was asked: $n + 1$ is the middle integer, so the sum is always 3 times the middle one (for example $11 + 12 + 13 = 36 = 3 \times 12$ ).

Worked example 2: an odd-number property

In this question you must show detailed reasoning.

Prove, using algebra, that for every odd integer $n$ , the number $n^2 + 3$ is a multiple of 4 but not a multiple of 8.

(4)

1. Let $n = 2k + 1$ , where $k$ is an integer. Then $n^2 + 3 = 4k^2 + 4k + 1 + 3 = 4k^2 + 4k + 4$ M1 (odd form, expanded)

2. $= 4(k^2 + k + 1)$ , so $n^2 + 3$ is a multiple of 4 A1

3. $k^2 + k = k(k + 1)$ is a product of two consecutive integers, one of which is even, so $k^2 + k$ is even and $k^2 + k + 1$ is odd dM1 (the reason, stated)

4. Write $k^2 + k + 1 = 2m + 1$ ; then $n^2 + 3 = 4(2m + 1) = 8m + 4$ , which leaves remainder 4 on division by 8. So for every odd integer $n$ , $n^2 + 3$ is a multiple of 4 but not a multiple of 8 A1*

Answer: $n^2 + 3 = 8m + 4$ for an integer $m$ .

As a check for yourself (not part of the proof), $n = 1, 3, 5$ give $4, 12, 28$ , which are $8m + 4$ with $m = 0, 1, 3$ .

Worked example 3: a "show that" and its "hence"

(a) Show that $(2k + 3)^2 - (2k + 1)^2 = 8(k + 1)$ . (2)

(b) Hence prove that the difference between the squares of any two consecutive odd numbers is a multiple of 8. (2)

1. (a) $(2k + 3)^2 - (2k + 1)^2 = (4k^2 + 12k + 9) - (4k^2 + 4k + 1)$ M1 (both squares expanded)

2. $= 8k + 8 = 8(k + 1)$ A1*

3. (b) Any two consecutive odd numbers can be written $2k + 1$ and $2k + 3$ for some integer $k$ , so by part (a) the difference of their squares is $8(k + 1)$ M1 (part (a) used, with the general form justified)

4. $k + 1$ is an integer, so the difference between the squares of any two consecutive odd numbers is a multiple of 8 A1*

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

Part (b) uses part (a) by recognising that every pair of consecutive odd numbers has the form in (a); for example $9^2 - 7^2 = 32 = 8 \times 4$ , with $k = 3$ .

Exam tip

Open every proof with a line that fixes the general form and says what the letter is: "Let $n = 2k + 1$ , where $k$ is an integer".

End with a sentence that repeats the statement in full ("so ...

for every odd integer $n$ ").

Examiners have reported that proofs which stop at the algebra, with no overall conclusion, lose the final mark.

Common mistakes

Checking numbers and calling it a proof. Five agreeing cases prove nothing about the sixth. Use a general form and algebra; numbers are only a private check.

Writing odd numbers as $4k + 1$ . It misses 3, 7, 11, ... . Use $2k + 1$ .

Writing $n = 2n + 1$ . That reuses the letter. Write $n = 2k + 1$ with a new letter $k$ .

One letter for two independent numbers. $2k + 1$ and $2k + 3$ are consecutive odd numbers, not any two odd numbers. For any two, use $2a + 1$ and $2b + 1$ .

Check your understanding

1. Prove that the product of any two odd integers is odd. (3) Total [3]

2. In this question you must show detailed reasoning. Prove that $n^3 - n$ is a multiple of 6 for every integer $n$ . (4) Total [4]

3. (a) Show that $(2k + 1)^2 - 1 = 4k(k + 1)$ . (2)
(b) Hence prove that the square of every odd integer is one more than a multiple of 8. (3) Total [5]

4. A student writes: "Let the odd number be $4k + 1$ , where $k$ is an integer. Then $(4k + 1)^2 = 16k^2 + 8k + 1 = 8(2k^2 + k) + 1$ , so the square of every odd number is one more than a multiple of 8."
(a) State an odd integer that cannot be written as $4k + 1$ for any integer $k$ . (1)
(b) State, giving a reason, whether the student has proved the result. (1) Total [2]

5. For each statement, state whether it is true for all real numbers $x$ .
(i) $x = 2 \Rightarrow x^2 = 4$
(ii) $x^2 = 4 \Rightarrow x = 2$
(iii) $x^2 = 4 \Leftrightarrow x = 2 \text{ or } x = -2$ (2) Total [2]

Answers

1. Let the integers be $2a + 1$ and $2b + 1$ , where $a$ and $b$ are integers B1; $(2a + 1)(2b + 1) = 4ab + 2a + 2b + 1$ M1; $= 2(2ab + a + b) + 1$ , and the bracket is an integer, so the product of any two odd integers is odd A1*

2. $n^3 - n = n(n^2 - 1) = (n - 1)n(n + 1)$ M1; these are three consecutive integers, at least one of which is even, so the product is a multiple of 2 A1; exactly one of any three consecutive integers is a multiple of 3, so the product is a multiple of 3 dM1; it is a multiple of both 2 and 3, which have no common factor, so $n^3 - n$ is a multiple of 6 for every integer $n$ A1*

3. (a) $(2k + 1)^2 - 1 = 4k^2 + 4k + 1 - 1$ M1; $= 4k^2 + 4k = 4k(k + 1)$ A1*
(b) Every odd integer is $2k + 1$ for an integer $k$ , so by (a) its square is $4k(k + 1) + 1$ M1; $k(k + 1)$ is a product of consecutive integers, so it is even: $k(k + 1) = 2m$ for an integer $m$ dM1; so $(2k + 1)^2 = 8m + 1$ , and the square of every odd integer is one more than a multiple of 8 A1*

4. (a) Any of $3, 7, 11, -1, \ldots$ , for example 3 B1
(b) No: the form $4k + 1$ covers only some of the odd integers (it misses 3, 7, 11, ...), so the argument proves the result only for those B1

5. (i) true; (ii) false, since $x = -2$ also gives $x^2 = 4$ ; (iii) true B1 for two correct, B1 for all three

The structure of a proof: from assumptions to a conclusion

Your course level