Questions on the structure of proof: deduction and exhaustion

Question 1

Write down general algebraic forms for: an even number, an odd number, and a pair of consecutive odd numbers. In each case say what the letter stands for.

Accepted Answer

An even number is 2n and an odd number is 2n + 1, where n is an integer. Consecutive odd numbers are 2n + 1 and 2n + 3. B1 for 2n, B1 for 2n + 1, B1 for the consecutive odd pair. Declaring that n is an integer is part of the answer, because the letter is there precisely to stand for every integer at once.

Question 2

A student checks that a claim holds for n = 1 to n = 50 and writes “proved”. Explain why the work is not a proof, and name the kind of argument that would be.

Accepted Answer

Fifty checks are evidence, and evidence is not proof: case 51 could still fail. A proof must be a general argument that covers every case at once, by deduction from known facts, or by exhaustion when the cases form a complete finite list. B1 for why fifty checks are not a proof, B1 for naming a general deductive argument.

Question 3

Write down the converse of the statement “if n is a multiple of 6 then n is a multiple of 3”, using arrow notation, and give a counter example showing the converse is false.

Accepted Answer

The original is “n is a multiple of 6” ⇒ “n is a multiple of 3”. Its converse reverses the arrow: “n is a multiple of 3” ⇒ “n is a multiple of 6”. B1 for the converse with the arrow written the right way round. Take n = 9: it is a multiple of 3 but not of 6. B1 for the counter example, B1 for checking both parts of it. So the converse is false, even though the original statement is true: a true implication can have a false converse.

Question 4

State what P ⇔ Q means in words, and explain what proving it requires that proving P ⇒ Q alone does not.

Accepted Answer

P ⇔ Q means “P if and only if Q”: each of P and Q forces the other. B1 for the meaning. Proving P ⇒ Q alone is one direction; an equivalence needs both directions proved, P ⇒ Q and also Q ⇒ P. B1 for stating that both directions are required.

Question 5

Prove that n² + 4n + 7 > 0 for all values of n.

Accepted Answer

Complete the square, giving n² + 4n + 7 = (n + 2)² + 3. A square is never negative, so (n + 2)² ≥ 0 and therefore (n + 2)² + 3 ≥ 3 > 0. M1 for completing the square, A1 for (n + 2)² + 3, B1 for the non-negative square. The sentence naming the square as non-negative is required, so the algebra alone is not the proof.

Question 6

Prove that the sum of any two consecutive odd numbers is divisible by 4.

Accepted Answer

Let the numbers be 2n + 1 and 2n + 3 for an integer n. Their sum is 4n + 4 = 4(n + 1), and n + 1 is an integer, so the sum is 4 times an integer. B1 for 2n + 1 and 2n + 3, M1 for forming the sum, A1 for 4(n + 1) with the conclusion. The final sentence matters: exhibiting the factor of 4 and saying the other factor is an integer is what “divisible by 4” means.

Question 7

Prove that the difference between the squares of any two consecutive odd numbers is divisible by 8.

Accepted Answer

Take the numbers as 2n + 1 and 2n + 3 for an integer n. Then (2n + 3)² − (2n + 1)² = (4n² + 12n + 9) − (4n² + 4n + 1) = 8n + 8 = 8(n + 1), which is 8 times an integer. B1 for the two forms, M1 for expanding and subtracting, A1 for 8n + 8, A1 for the conclusion. Expanding both squares fully before subtracting keeps the sign errors out, and the difference of two squares gives the same result in one line: (4n + 4)(2) = 8(n + 1). Testing 3 and 5 proves nothing on its own.

Question 8

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

Accepted Answer

Every integer is even or odd, so two cases cover everything. If k = 2n then k² = 4n², a multiple of 4. If k = 2n + 1 then k² = 4n² + 4n + 1 = 4(n² + n) + 1, one more than a multiple of 4. B1 for splitting into even and odd, M1 for squaring each case, A1 for the even case, A1 for the odd case. This is proof by exhaustion over types rather than individual numbers.

Question 9

State whether “x = 3” is necessary, sufficient, both or neither for “x² = 9”, justifying your answer, and write the relationship using an arrow.

Accepted Answer

x = 3 ⇒ x² = 9, since 3² = 9: so x = 3 is sufficient for x² = 9. B1 for the arrow, B1 for confirming it numerically. But x² = 9 does not force x = 3, since x = −3 also gives x² = 9 while x ≠ 3, so x = 3 is not necessary for x² = 9. B1 for the counter example x = −3, B1 for the conclusion, sufficient but not necessary. A necessary and sufficient condition for x² = 9 would have to allow x = −3 as well.

Question 10

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

Accepted Answer

Let the numbers be 2n and 2n + 2 for an integer n. Their product is 2n(2n + 2) = 4n(n + 1). B1 for the two forms, M1 for the product 4n(n + 1). Of the two consecutive integers n and n + 1, one is always even, so n(n + 1) is always a multiple of 2: write n(n + 1) = 2m for an integer m. A1 for that reasoning. Then 4n(n + 1) = 4 × 2m = 8m, a multiple of 8. A1 for the conclusion.

Question 11

Prove that the sum of the squares of any two consecutive integers is always odd.

Accepted Answer

Let the integers be n and n + 1 for an integer n. Their sum of squares is n² + (n + 1)² = n² + n² + 2n + 1 = 2n² + 2n + 1 = 2(n² + n) + 1. B1 for the two forms, M1 for expanding, A1 for 2(n² + n) + 1. Since n² + n is an integer, the sum is 2 times an integer plus 1, which is what odd means. A1 for the conclusion. No case split is needed here: the parity of n never enters the argument.

Question 12

Given that p is a prime number with 5 < p < 20, prove by exhaustion that p² − 1 is divisible by 24.

Accepted Answer

The complete list is 7, 11, 13, 17, 19. In turn, p² − 1 gives 48, 120, 168, 288, 360, and dividing by 24 gives 2, 5, 7, 12, 15, all integers. Every case on the complete list has been checked, so the claim is proved. B1 for the complete list, M1 for computing p² − 1, A1 for the five values, A1 for dividing by 24, B1 for the concluding statement.

Question 13

Explain why proof by exhaustion could not be used to prove that n² + 4n + 7 > 0 for all integers n, even in principle.

Accepted Answer

Exhaustion needs a complete finite list of cases, and the integers go on for ever: however many are checked, infinitely many remain. B1 for exhaustion needing a finite list, B1 for the integers being infinite. A claim about all integers needs a general argument, so the deduction proof via the completed square is the only route.

Question 14

f(n) = n⁴ − 5n² + 4. Prove by exhaustion that f(n) = 0 for each of n = −2, −1, 1, 2, and explain why this does not by itself prove that f(n) = 0 has no other solution.

Accepted Answer

Substituting each value: f(−2) = 16 − 20 + 4 = 0, f(−1) = 1 − 5 + 4 = 0, f(1) = 1 − 5 + 4 = 0, f(2) = 16 − 20 + 4 = 0. M1 for substituting all four values, A1 for all four giving 0. Every case in this list has been checked, so f(n) = 0 for each of them. Exhaustion over a list proves only that the listed values are roots; it says nothing about whether other values are roots too, since the list was never claimed to be complete for that wider question. B1 for that distinction. Here the wider claim can still be settled: f(n) = (n² − 1)(n² − 4), which is zero exactly when n² = 1 or n² = 4, that is n = ±1 or n = ±2, and no other real number. A1 for the factorisation, B1 for concluding that these four are the only roots.

Question 15

A three-digit number is n = 100a + 10b + c, where a, b and c are its digits and a ≠ 0. Prove that n is divisible by 9 if and only if a + b + c is divisible by 9, and check your result on n = 738.

Accepted Answer

n − (a + b + c) = 100a + 10b + c − a − b − c = 99a + 9b = 9(11a + b). M1 for forming the difference, M1 for the regrouping, A1 for 9(11a + b). This difference is a multiple of 9 whatever the digits are, since 11a + b is an integer. B1 for that observation. So n and a + b + c differ by a multiple of 9, which means one is a multiple of 9 exactly when the other is: if n = 9k then a + b + c = n − 9(11a + b) = 9(k − 11a − b), and the same argument runs the other way. A1 for stating both directions follow from the single identity. n is divisible by 9 ⇔ a + b + c is divisible by 9. For n = 738, the digit sum is 7 + 3 + 8 = 18, and both 738 = 9 × 82 and 18 = 9 × 2 are multiples of 9, confirming the equivalence. B1 for the check.