Mathematical proof solutions

✎ Practise these questions 📖 Revision notes All solution banks

Every question on this topic with its answer, the working, and a full method: what the question is testing, the reason for each step, the mistakes that are easy to make and what they would give you, and the principle to take away.

1. PRF-01Mathematical proof · spec Prf1 · Paper 2 style · ★☆☆

Consider the claim: for every positive integer \(n\), \(n^2 + n\) is even. Which of the following is a complete and valid proof?

A\(n^2 + n\) is even because both \(n^2\) and \(n\) are even.
BIf \(n\) is even then \(n^2\) is even and so \(n^2 + n\) is even.
CSuppose \(n^2 + n\) is odd. Then \(n\) is odd, so \(n^2\) is odd, so \(n^2 + n\) is even, which is a contradiction... unless \(n\) is even.
D\(1^2 + 1 = 2\), \(2^2 + 2 = 6\), \(3^2 + 3 = 12\), which are all even, so the claim holds.
E\(n^2 + n = n(n + 1)\) is the product of two consecutive integers, one of which must be even, so the product is even.

Answer: E. The factorised argument covers every \(n\) at once: \(n(n+1)\) is a product of consecutive integers, so one factor is even. Checking \(n = 1, 2, 3\) is only three cases; 'if \(n\) is even ...' leaves odd \(n\) untreated; 'both \(n^2\) and \(n\) are even' is false for odd \(n\); and the contradiction attempt ends with an unresolved exception.

Full method — how and why

What makes a proof complete: it must cover every case in the claim with a general argument, not a sample of values.

The claim is about every positive integer, so any valid proof must handle all \(n\) at once.
Checking particular values can only ever disprove a universal claim, never prove one.
Factorise: \(n^2 + n = n(n+1)\) - the product of two consecutive integers.
Factorising turns a statement about a sum into one about a product, where parity is easy to control.
Of any two consecutive integers, exactly one is even; an even factor makes the product even.
This single sentence covers both the case \(n\) even and the case \(n\) odd - no case-splitting needed.
That argument is general and complete, so it is the proof.
Now examine why the others fail, which is the real content of the question.

Where it goes wrong

Accepting the check of \(n = 1, 2, 3\): three cases out of infinitely many prove nothing.
Accepting 'if \(n\) is even then \(n^2+n\) is even' - true, but it leaves odd \(n\) untreated, so the proof is incomplete.
Accepting 'both \(n^2\) and \(n\) are even' - simply false when \(n\) is odd.
Accepting the contradiction attempt that ends 'unless \(n\) is even' - a proof cannot end with an unresolved exception.

Takeaway A proof of 'for all \(n\)' must be general. Examples illustrate; only argument proves.

2. PRF-02Mathematical proof · spec Prf1 · Paper 2 style · ★☆☆

Which of the following is a counterexample to the claim 'if \(n\) is a positive integer, then \(2^n + 1\) is prime'?

A\(n = 8\)
B\(n = 1\)
C\(n = 4\)
D\(n = 3\)
E\(n = 2\)

Answer: D. \(2^3 + 1 = 9 = 3 \times 3\) is not prime. (\(n = 1, 2, 4, 8\) give \(3, 5, 17, 257\), all prime.)

Full method — how and why

To disprove a universal claim, find one value where the conclusion fails - so test values until one breaks.

Evaluate \(2^n+1\) for each candidate: \(n=1 \to 3\), \(n=2 \to 5\), \(n=3 \to 9\), \(n=4 \to 17\), \(n=8 \to 257\).
Systematic evaluation is faster than trying to be clever here.
\(9 = 3 \times 3\) is not prime, so \(n = 3\) breaks the claim.
That is the counterexample: hypothesis satisfied (\(3\) is a positive integer), conclusion false.
The others - \(3, 5, 17, 257\) - are all prime, so none of them refutes anything.
(\(257\) is prime: it is not divisible by \(2,3,5,7,11,13\), and \(17^2 = 289 > 257\).)

Where it goes wrong

Assuming a large value like \(n = 8\) must fail because the numbers get big - size is not the issue.
Stopping at the first odd value of \(2^n+1\); every one of them is odd, since \(2^n\) is even.

Takeaway Notice the pattern: \(2^n+1\) can only be prime when \(n\) is a power of \(2\) - and \(3\) is not, which is exactly why it fails.

3. PRF-03Mathematical proof · spec Prf1 · Paper 2 style · ★☆☆

Here is a proof that \(\sqrt{2}\) is irrational, with its steps in the wrong order.

IThen \(p^2 = 2q^2\), so \(p^2\) is even, so \(p\) is even; write \(p = 2k\).
IISuppose, for contradiction, that \(\sqrt2 = \dfrac{p}{q}\) where \(p\) and \(q\) are positive integers with no common factor.
IIIThis contradicts the assumption that \(p\) and \(q\) have no common factor, so \(\sqrt2\) is irrational.
IVThen \(4k^2 = 2q^2\), so \(q^2 = 2k^2\) is even, so \(q\) is even.

Which is the correct order?

AII, I, IV, III
BI, II, IV, III
CII, IV, I, III
DI, IV, II, III
EII, I, III, IV

Answer: A. Assume (II), deduce \(p\) even (I), deduce \(q\) even (IV), reach the contradiction (III).

Full method — how and why

Ordering a proof by contradiction. The logical skeleton is fixed: assume the opposite, deduce consequences, hit the contradiction.

The assumption must come first: II sets up \(\sqrt2 = \frac pq\) in lowest terms.
Nothing can be deduced before the supposition is made, and 'no common factor' is the condition that will later be contradicted.
Next I: squaring gives \(p^2 = 2q^2\), so \(p^2\) is even, so \(p\) is even, \(p = 2k\).
It depends on II, and it introduces \(k\), which IV uses.
Then IV: substituting \(p = 2k\) gives \(4k^2 = 2q^2\), so \(q^2 = 2k^2\) is even, so \(q\) is even.
IV cannot precede I because it uses \(k\), which I defines.
Finally III: \(p\) and \(q\) are both even, contradicting 'no common factor'. Hence \(\sqrt2\) is irrational.
The conclusion must come after both parities are established. Order: II, I, IV, III.

Where it goes wrong

Placing III before IV - the contradiction needs \(q\) even too, so it cannot come earlier.
Starting with I, which refers to \(p\) and \(q\) before they have been introduced.

Takeaway Order a proof by dependency: each line may only use things already defined or deduced.

4. PRF-04Mathematical proof · spec Prf1 · Paper 2 style · ★☆☆

A student wants to prove that the square of any odd integer leaves remainder \(1\) when divided by \(8\). Which of the following is the most appropriate first step?

ACheck the claim for \(1, 3, 5, 7\) and \(9\).
BAssume the square leaves a remainder other than \(1\).
CAssume the claim is true for all odd integers.
DWrite the odd integer as \(2k\) for some integer \(k\).
EWrite the odd integer as \(2k + 1\) for some integer \(k\).

Answer: E. A direct proof: \((2k+1)^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1\), and \(k(k+1)\) is even, so the square is \(8m + 1\). Checking cases is not a proof; assuming the claim is circular.

Full method — how and why

Choosing a proof strategy. For a 'for all odd integers' claim, the standard opening is an algebraic parametrisation.

Represent an arbitrary odd integer as \(2k+1\), \(k\) an integer.
This one expression covers every odd integer, which is what a universal claim needs.
(For context, the proof then runs: \((2k+1)^2 = 4k^2+4k+1 = 4k(k+1)+1\).)
Factorising \(4k^2+4k\) as \(4k(k+1)\) exposes the consecutive pair.
\(k(k+1)\) is a product of consecutive integers, hence even, say \(2m\), so the square is \(8m+1\).
That is remainder \(1\) on division by \(8\), as claimed.

Where it goes wrong

Checking \(1,3,5,7,9\) - evidence, not proof.
Writing the odd integer as \(2k\), which is the form of an even integer.
Assuming the claim is true - circular.
Reaching for contradiction ('assume the remainder is not \(1\)'): legal, but here a direct proof is simpler, and the question asks for the most appropriate step.

Takeaway Universal claims about odd/even numbers start by writing the general form: \(2k\) or \(2k+1\).

5. PRF-07Mathematical proof · spec Prf1 · Paper 2 style · ★☆☆

Prove by cases that \(n^3 - n\) is divisible by \(3\) for every integer \(n\). Which set of cases is both sufficient and necessary to consider?

A\(n = 3k + 1\), \(n = 3k + 2\)
B\(n\) even, \(n\) odd
C\(n\) positive, \(n\) zero, \(n\) negative
D\(n = 3k\), \(n = 3k + 1\), \(n = 3k + 2\)
E\(n\) prime, \(n\) not prime

Answer: D. \(n^3 - n = (n - 1)n(n + 1)\) is a product of three consecutive integers; splitting by remainder on division by \(3\) shows one factor is a multiple of \(3\) in every case.

Full method — how and why

Proof by exhaustive cases: the cases must cover every integer (sufficient) with none redundant (necessary), and they must be chosen to match the divisor in question.

The claim is about divisibility by \(3\), so split by remainder on division by \(3\): \(n = 3k\), \(3k+1\), \(3k+2\).
Every integer has exactly one of these three forms, so the cases are exhaustive and non-overlapping.
Check each: \(n^3 - n = (n-1)n(n+1)\). If \(n = 3k\) the middle factor is a multiple of \(3\); if \(n = 3k+1\) then \(n - 1 = 3k\); if \(n = 3k+2\) then \(n+1 = 3(k+1)\).
Three consecutive integers always include a multiple of \(3\) - the case split makes that explicit.
So the product is divisible by \(3\) in every case.
The proof is complete because the cases cover all integers.

Where it goes wrong

Splitting into even/odd - that is the wrong modulus and tells you nothing about divisibility by \(3\).
Using only \(3k+1\) and \(3k+2\), which omits the multiples of \(3\) themselves - not exhaustive.
Splitting by sign or by primality: exhaustive, but useless for this claim.

Takeaway For divisibility by \(m\), split into the \(m\) residue classes \(mk, mk+1, \ldots, mk+(m-1)\).

6. PRF-08Mathematical proof · spec Prf2 · Paper 2 style · ★☆☆

It is given that for all real \(x\): if \(f(x) > 0\) then \(g(x) > 0\). It is also known that \(g(2) = -1\). What can be deduced?

A\(f(2) < 0\)
B\(f(2) = 0\)
C\(f(2) > 0\)
D\(f(2) \leq 0\)
Enothing about \(f(2)\)

Answer: D. Contrapositive: if \(g(x) \leq 0\) then \(f(x) \leq 0\). Since \(g(2) = -1 \leq 0\), \(f(2) \leq 0\) (it could be \(0\) or negative).

Full method — how and why

Deduction from an implication. You are given information about the conclusion, so the contrapositive is the tool.

The given rule is \(f(x)>0 \Rightarrow g(x)>0\).
It lets you conclude about \(g\) from \(f\), not the other way round - directly, at least.
Its contrapositive is: \(g(x) \leq 0 \Rightarrow f(x) \leq 0\), which is equally valid.
Negate and swap: \(\neg(g>0)\) is \(g \leq 0\), \(\neg(f>0)\) is \(f \leq 0\).
Apply it at \(x = 2\): \(g(2) = -1 \leq 0\), so \(f(2) \leq 0\).
That is all that follows - \(f(2)\) could be \(0\) or negative.

Where it goes wrong

Concluding \(f(2) < 0\) - too strong; the negation of \(>0\) includes \(=0\).
Concluding nothing, forgetting that the contrapositive is always available.
Concluding \(f(2) > 0\) by using the implication backwards (affirming the consequent).

Takeaway Information about the conclusion of an implication is used via the contrapositive - and mind the boundary: \(\neg(x>0)\) is \(x \leq 0\).

7. PRF-13Mathematical proof · spec Prf1 · Paper 2 style · ★☆☆

Which of the following is a correct proof that the sum of any three consecutive integers is divisible by \(3\)?

AAny three integers include one that is a multiple of \(3\), so the sum is a multiple of \(3\).
BLet the integers be \(n - 1\), \(n\), \(n + 1\). Their sum is \(3n\), which is divisible by \(3\).
CLet the integers be \(n\), \(2n\), \(3n\). Their sum is \(6n\), which is divisible by \(3\).
DThe middle integer is the mean of the three, so the sum is three times an integer... but this needs the middle integer to be a multiple of \(3\).
E\(1 + 2 + 3 = 6\), \(2 + 3 + 4 = 9\) and \(3 + 4 + 5 = 12\) are all divisible by \(3\).

Answer: B. Writing the three as \(n-1, n, n+1\) gives the sum \(3n\) for every integer \(n\) - general and correct. Checking \(1+2+3\), \(2+3+4\), \(3+4+5\) is only cases; \(n, 2n, 3n\) are not consecutive; and 'any three integers include a multiple of \(3\)' is invalid reasoning (containing a multiple of \(3\) does not make the sum one).

Full method — how and why

Choosing the right algebraic representation is most of the work. Centre the variables on the middle term.

Represent three consecutive integers as \(n-1\), \(n\), \(n+1\).
Centring on \(n\) makes the \(\pm1\) cancel; \(n, n+1, n+2\) also works but gives \(3n+3\), needing one more line.
Add: \((n-1) + n + (n+1) = 3n\).
The \(-1\) and \(+1\) cancel.
\(3n\) is \(3\) times an integer, hence divisible by \(3\), for every integer \(n\).
General, so it is a proof.

Where it goes wrong

Using \(n, 2n, 3n\) - those are multiples, not consecutive integers.
Checking three numerical cases.
Arguing 'any three integers include a multiple of \(3\)' - false for \(1,2,4\), and in any case containing a multiple of \(3\) would not make the sum a multiple of \(3\).
The 'mean' argument that ends by demanding the middle integer be a multiple of \(3\) - it confuses '\(3 \times\) an integer' with '\(3 \times\) a multiple of \(3\)'.

Takeaway Consecutive integers: use \(n-1, n, n+1\). Their sum is \(3n\), always divisible by \(3\).

8. PRF-14Mathematical proof · spec Prf1 · Paper 2 style · ★☆☆

To prove 'if \(n^2\) is even then \(n\) is even' by contradiction, which assumption should be made?

A\(n\) is odd.
B\(n^2\) is even and \(n\) is odd.
C\(n^2\) is even.
D\(n^2\) is odd.
E\(n\) is even and \(n^2\) is odd.

Answer: B. Assume the hypothesis holds and the conclusion fails, then derive a contradiction: \(n\) odd gives \(n^2\) odd, contradicting \(n^2\) even.

Full method — how and why

Setting up a proof by contradiction for an implication: assume the hypothesis and the negated conclusion.

The claim is 'if \(n^2\) is even then \(n\) is even': hypothesis \(n^2\) even, conclusion \(n\) even.
Identify both parts before negating anything.
For contradiction, suppose the whole implication fails. An implication fails only when the hypothesis holds and the conclusion does not.
This is the one case that would make \(A \Rightarrow B\) false.
So assume: \(n^2\) is even and \(n\) is odd.
Both, not just one.
(The proof then runs: \(n = 2k+1 \Rightarrow n^2 = 4k^2+4k+1\), odd - contradicting \(n^2\) even.)
The contradiction is with the retained hypothesis.

Where it goes wrong

Assuming only '\(n\) is odd' and dropping the hypothesis - then there is nothing to contradict.
Assuming '\(n^2\) is odd', which negates the hypothesis instead of the conclusion.
Assuming '\(n\) even and \(n^2\) odd', which negates the wrong part of each.

Takeaway To contradict \(A \Rightarrow B\), assume \(A\) and \(\neg B\) - keep the hypothesis, negate only the conclusion.

9. PRF-16Mathematical proof · spec Prf4 · Paper 2 style · ★☆☆

A proof that if \(a\) and \(b\) are positive real numbers then \(\dfrac{a + b}{2} \geq \sqrt{ab}\) is given with its lines scrambled.

IHence \(a + b \geq 2\sqrt{ab}\), and dividing by \(2\) gives the result.
IIExpanding, \(a - 2\sqrt{ab} + b \geq 0\).
IIISince squares are non-negative, \((\sqrt a - \sqrt b)^2 \geq 0\).

Which order gives a valid proof?

AIII, II, I
BI, II, III
CII, III, I
DIII, I, II
EII, I, III

Answer: A. Start from a known truth (III), expand (II), rearrange (I). Starting from the result and working backwards (I, II, III) would need every step to be reversible and is presented in the wrong direction.

Full method — how and why

Direction matters. A proof should start from something known and deduce the result, not start from the result.

Start with a known truth: \((\sqrt a - \sqrt b)^2 \geq 0\), valid because squares are non-negative and \(\sqrt a, \sqrt b\) exist for \(a, b > 0\). That is III.
Beginning from an undeniable fact is the safe way round.
Expand it: \(a - 2\sqrt{ab} + b \geq 0\). That is II.
\((\sqrt a)^2 = a\), \((\sqrt b)^2 = b\), and the cross term is \(-2\sqrt a\sqrt b = -2\sqrt{ab}\).
Rearrange: \(a + b \geq 2\sqrt{ab}\), then divide by \(2\). That is I.
Dividing by the positive number \(2\) preserves the inequality.
Order: III, II, I.
Known truth \(\to\) algebra \(\to\) required result.

Where it goes wrong

Choosing I, II, III - that starts by assuming the result. Working backwards is a legitimate way to find a proof, but to present one every step must be reversed.
Starting with II, whose inequality has not yet been justified.

Takeaway Present proofs forwards, from an established fact to the conclusion. This one proves AM \(\geq\) GM.

10. PRF-17Mathematical proof · spec Prf1 · Paper 2 style · ★☆☆

Which of the following claims is FALSE, and therefore can be disproved by a counterexample?

AIf \(a > b\) then \(a + c > b + c\), for all real \(a, b, c\).
BIf \(a > b\) then \(a^2 > b^2\), for all real \(a, b\).
CIf \(a > b > 0\) then \(a^2 > b^2\).
DIf \(a > b\) then \(a^3 > b^3\), for all real \(a, b\).
EIf \(a > b\) then \(-a < -b\), for all real \(a, b\).

Answer: B. \(a = 1\), \(b = -2\): \(1 > -2\) but \(1 < 4\). The others are true.

Full method — how and why

Scan the claims for the one that squaring breaks - negative numbers are where inequalities misbehave.

'\(a>b \Rightarrow a^2 > b^2\) for all real \(a,b\)': try \(a = 1\), \(b = -2\). Then \(1 > -2\) but \(1 < 4\). False.
Squaring reverses order once negatives with larger magnitude are involved.
'\(a > b > 0 \Rightarrow a^2 > b^2\)' is true - the positivity condition is exactly what the first claim lacked.
Comparing the two shows precisely which hypothesis does the work.
'\(a>b \Rightarrow a+c > b+c\)' is true: adding the same number to both sides preserves order.
Valid for every real \(c\), positive or negative.
'\(a>b \Rightarrow a^3>b^3\)' is true: cubing is strictly increasing for every real number, unlike squaring.
\(x^3\) keeps the sign of \(x\), so no reversal occurs.
'\(a>b \Rightarrow -a < -b\)' is true: multiplying by \(-1\) reverses the inequality.
The standard sign rule.

Where it goes wrong

Thinking the cubing claim fails - it does not; only even powers destroy order.
Thinking multiplying by \(-1\) keeps the direction.

Takeaway Squaring preserves order only for non-negative numbers; cubing, adding and negating (with a flip) always behave.

11. PRF-20Mathematical proof · spec Prf3 · Paper 2 style · ★☆☆

\(T_n\) denotes the \(n\)th triangular number \(\dfrac{n(n+1)}{2}\). A student observes \(T_1 + T_2 = 4\), \(T_2 + T_3 = 9\), \(T_3 + T_4 = 16\) and conjectures that \(T_n + T_{n+1}\) is always a perfect square. Which of the following proves the conjecture?

A\(T_n + T_{n+1} = \dfrac{n(n+1) + (n+1)(n+2)}{2} = \dfrac{(n+1)(2n+2)}{2} = (n+1)^2\)
B\(T_n + T_{n+1} = 2T_n + (n + 1)\), which is a square.
CTriangular numbers are always squares.
D\(T_4 + T_5 = 25\), which is a square, so the pattern continues.
E\(T_{n+1} - T_n = n + 1\), so the sum is a square.

Answer: A. Only the algebraic verification \(T_n + T_{n+1} = \frac{(n+1)(2n+2)}{2} = (n+1)^2\) is general; the rest check one more case, assert something false, or state a true identity without showing the result.

Full method — how and why

Proving a conjecture about a sequence: substitute the formula and simplify algebraically to a general result.

Write both terms: \(T_n = \dfrac{n(n+1)}{2}\) and \(T_{n+1} = \dfrac{(n+1)(n+2)}{2}\).
Replace \(n\) by \(n+1\) throughout the given formula.
Add over the common denominator: \(\dfrac{n(n+1) + (n+1)(n+2)}{2}\).
Same denominator, so just add numerators.
Factor out \((n+1)\): \(\dfrac{(n+1)\left[n + (n+2)\right]}{2} = \dfrac{(n+1)(2n+2)}{2}\).
Spotting the common factor avoids expanding and re-factorising.
\(2n+2 = 2(n+1)\), so the expression is \((n+1)^2\) - a perfect square for every \(n\). Proved.
The \(2\) cancels the denominator.

Where it goes wrong

Checking \(T_4 + T_5 = 25\) and stopping - one more case is still not a proof.
'Triangular numbers are always squares' - plainly false (\(T_2 = 3\)).
'\(T_n + T_{n+1} = 2T_n + (n+1)\), which is a square' - the identity is right but the conclusion is asserted, not shown.
Quoting the difference \(T_{n+1} - T_n = n+1\), which is true but says nothing about the sum.

Takeaway Substitute the general formula and simplify; consecutive triangular numbers sum to \((n+1)^2\).

12. X2-27Mathematical proof · spec Prf1 · Paper 2 style · ★☆☆

Consider the claim: if \(n\) is a positive integer then \(n^2 + n + 1\) is odd. Which of the following is a valid proof?

A\(n^2 + n = n(n + 1)\) is even, being the product of consecutive integers, so \(n^2 + n + 1\) is even plus one, which is odd.
B\(n^2 + n + 1\) cannot be factorised, so it is odd.
CFor \(n = 1, 2, 3\) the values are \(3, 7, 13\), all odd, so the claim holds.
DSuppose \(n^2 + n + 1\) is even. Then \(n\) is even, which is a contradiction.
EIf \(n\) is odd then \(n^2\) is odd and \(n\) is odd, so \(n^2 + n + 1\) is odd.

Answer: A. The argument from \(n^2 + n = n(n+1)\) being even is direct and general. Checking \(n = 1,2,3\) is only cases; 'cannot be factorised' is irrelevant to parity; 'if \(n\) is odd ...' says nothing about even \(n\); and the contradiction attempt never reaches a contradiction, since \(n\) may well be even.

Full method — how and why

Same 'which is a valid proof' pattern as PRF-01: general argument versus cases, irrelevance and incompleteness.

The valid proof: \(n^2+n = n(n+1)\) is a product of consecutive integers, hence even; adding \(1\) gives an odd number.
General, covering every positive integer with no case split.
Checking \(n=1,2,3\) gives \(3,7,13\) - evidence, not proof.
Three cases out of infinitely many.
'It cannot be factorised, so it is odd' - factorisability has nothing to do with parity (\(6 = 2\times3\) and \(9=3\times3\) are respectively even and odd).
An irrelevant premise cannot support the conclusion.
'If \(n\) is odd then ... so \(n^2+n+1\) is odd' - correct but only for odd \(n\); even \(n\) is untreated. Incomplete.
A case-based proof must cover every case.
'Suppose \(n^2+n+1\) is even. Then \(n\) is even, contradiction' - \(n\) being even is not a contradiction; \(n\) can be even.
A contradiction proof must actually reach an impossibility.

Where it goes wrong

Accepting the odd-\(n\) argument because every line in it is true - truth is not completeness.
Accepting the contradiction attempt because it uses the right vocabulary.

Takeaway \(n(n+1)\) is always even, so \(n^2+n+1\) is always odd. A proof must be general, relevant and complete.

13. PRF-05Mathematical proof · spec Prf3 · Paper 2 style · ★★☆

The sums \(1\), \(1 + 3\), \(1 + 3 + 5\), \(1 + 3 + 5 + 7\) are \(1, 4, 9, 16\). A student conjectures that the sum of the first \(n\) odd numbers is \(n^2\). Which of the following is a valid justification?

AEach odd number is one more than an even number, and the even numbers sum to \(n(n-1)\)... so the total is \(n^2\) since there are \(n\) of them: \(n(n - 1) + n = n^2\).
BThe conjecture is true because \(n^2\) is always odd when \(n\) is odd.
CThe pattern \(1, 4, 9, 16\) continues with \(25\), so the conjecture is true.
DThe odd numbers form an arithmetic series with first term \(1\) and difference \(2\), so the sum of \(n\) terms is \(\frac n2(2 + 2(n - 1)) = n^2\).
EFour cases have been checked, which is enough for a pattern.

Answer: D. The arithmetic-series argument applies \(S_n = \frac n2(2a + (n-1)d)\) to every \(n\) and simplifies to \(n^2\). (The even-numbers argument also reaches a correct total, but extending the pattern to \(25\), the remark about \(n^2\) being odd, and 'four cases is enough' are not justifications at all.)

Full method — how and why

Distinguishing a justification from a pattern-spot. The valid answer must establish the formula for all \(n\).

The first \(n\) odd numbers are \(1, 3, 5, \ldots\) - an arithmetic series with \(a = 1\), \(d = 2\).
Recognising the structure is what lets a general formula apply.
Apply \(S_n = \frac n2\left(2a + (n-1)d\right) = \frac n2(2 + 2(n-1))\).
The standard arithmetic-series sum, valid for every \(n\).
Simplify: \(\frac n2 \times 2n = n^2\).
\(2 + 2n - 2 = 2n\).
That holds for all \(n\), so it justifies the conjecture.
By contrast, 'the pattern continues with \(25\)' checks one more case, and 'four cases is enough' explicitly is not a proof.

Where it goes wrong

Accepting 'four cases have been checked' - the whole point of this topic is that it is not enough.
Accepting '\(n^2\) is odd when \(n\) is odd' - a true but completely irrelevant statement.
Being drawn to the even-numbers argument; its calculation happens to work out, but it is presented with an unjustified aside, whereas the series argument is clean and standard.

Takeaway A justification must apply to every \(n\); extending a pattern one more term never does.

14. PRF-06Mathematical proof · spec Prf1 · Paper 2 style · ★★☆

Which of the following statements can be disproved by a single counterexample?

IEvery prime number greater than \(2\) is odd.
IIEvery integer of the form \(4k + 3\) is prime.
IIIThere exists an even prime number.

Anone of them
BI only
CII only
DIII only
EI and II only
FI and III only
GII and III only
HI, II and III

Answer: C. Only a 'for all' statement can be disproved by one counterexample. I is true (no counterexample exists). II is false and \(k = 3\) (\(15\)) disproves it. III is an existence statement - a counterexample is meaningless; it is proved by the example \(2\).

Full method — how and why

Only a universal statement that is false can be disproved by a counterexample. Two separate tests.

I: 'every prime \(> 2\) is odd' is universal - but it is true (any even number \(>2\) has factor \(2\)), so no counterexample exists.
You cannot disprove a true statement.
II: 'every integer \(4k+3\) is prime' is universal and false: \(k = 3\) gives \(15 = 3 \times 5\). Disprovable. Yes.
One failing case is a counterexample.
III: 'there exists an even prime' is existential, not universal - and it is true (\(2\)). A counterexample is not even the right tool.
To disprove an existential statement you would have to rule out every case, which is not a 'single counterexample'.
So II only.
Match to the list.

Where it goes wrong

Including I because it is a 'for all' statement - the statement also has to be false.
Including III by confusing what disproves an existential claim.

Takeaway Counterexamples disprove false universal statements only. Existential statements are proved by example and disproved only by a general argument.

15. PRF-09Mathematical proof · spec Prf1 · Paper 2 style · ★★☆

Here is a proof that there are infinitely many primes, with the steps out of order.

IThen \(N\) leaves remainder \(1\) on division by each of \(p_1, \ldots, p_n\), so no \(p_i\) divides \(N\).
IISuppose there are only finitely many primes \(p_1, p_2, \ldots, p_n\), and let \(N = p_1 p_2 \cdots p_n + 1\).
IIISo \(N\) has a prime factor that is not in the list, which is a contradiction.
IVBut \(N > 1\), so \(N\) has at least one prime factor.

Which is the correct order?

AII, I, IV, III
BII, III, I, IV
CI, II, IV, III
DII, I, III, IV
EIV, II, I, III

Answer: A. Define \(N\) (II), show no listed prime divides it (I), note that \(N\) nevertheless has some prime factor (IV), and conclude that this factor is a new prime (III). The conclusion III cannot come before both I and IV have been established.

Full method — how and why

Ordering Euclid's proof. Again the skeleton is assume-deduce-contradict, and the dependencies fix the order.

II first: assume finitely many primes \(p_1,\ldots,p_n\) and construct \(N = p_1p_2\cdots p_n + 1\).
Everything else refers to \(N\), so it must be defined first.
Then I: each \(p_i\) divides \(p_1\cdots p_n\), so dividing \(N\) by \(p_i\) leaves remainder \(1\) - no listed prime divides \(N\).
This is the key property of the \(+1\).
Then IV: \(N > 1\), so it has at least one prime factor.
Every integer greater than \(1\) has a prime factor - a separate fact, independent of I.
Finally III: that prime factor is not in the list, contradicting the assumption that the list was complete. Order: II, I, IV, III.
The contradiction needs both I (none of the listed primes works) and IV (some prime does).

Where it goes wrong

Putting III immediately after II, before either supporting fact has been established.
Thinking the proof claims \(N\) is prime - it need not be; it merely has a prime factor outside the list.

Takeaway In a contradiction proof, the contradiction is the last line, and it must rest on everything before it.

16. PRF-10Mathematical proof · spec Prf1 · Paper 2 style · ★★☆

Consider the claim: if \(x\) and \(y\) are real numbers with \(x + y > 10\), then \(x > 5\) or \(y > 5\). Which of the following proves it?

ASuppose \(x \leq 5\) and \(y \leq 5\). Then \(x + y \leq 10\), contradicting \(x + y > 10\).
BSuppose \(x > 5\). Then \(y > 10 - x\), so \(y > 5\).
CIf \(x + y > 10\) then the average of \(x\) and \(y\) is more than \(5\), so both exceed \(5\).
DTake \(x = 6\), \(y = 6\): then \(x + y = 12 > 10\) and \(x > 5\).
EIf \(x > 5\) then the conclusion holds; if \(y > 5\) then the conclusion holds.

Answer: A. Supposing \(x \leq 5\) and \(y \leq 5\) and deriving \(x + y \leq 10\) is a valid proof by contradiction. 'If \(x>5\) then the conclusion holds' assumes the conclusion; \(x = y = 6\) is a single example; 'suppose \(x>5\), then \(y>5\)' proves something false; and the averaging argument ends with 'both exceed \(5\)', which is wrong.

Full method — how and why

Proving 'if \(P\) then (\(A\) or \(B\))'. Assuming both \(A\) and \(B\) fail and deriving a contradiction is the natural route.

Negate the conclusion: 'not (\(x>5\) or \(y>5\))' means \(x \leq 5\) and \(y \leq 5\) (De Morgan).
Negating an 'or' gives an 'and' - and it gives you two usable facts instead of a disjunction.
Add the inequalities: \(x + y \leq 10\).
Inequalities of the same direction may be added.
That contradicts the hypothesis \(x+y > 10\), so the conclusion must hold.
Hypothesis true and conclusion false is impossible, which is exactly what proves the implication.

Where it goes wrong

'If \(x>5\) then the conclusion holds' - this assumes part of what is to be proved.
Testing \(x = y = 6\) - a single example proves nothing about all \(x, y\).
'Suppose \(x > 5\), then \(y > 10 - x\), so \(y > 5\)' - the algebra is wrong and it proves a false statement (both exceeding \(5\)).
'The average exceeds \(5\) so both exceed \(5\)' - the average exceeding \(5\) only forces at least one to.

Takeaway To prove an 'or', negate it into an 'and' and look for a contradiction - De Morgan turns a weak conclusion into strong assumptions.

17. PRF-11Mathematical proof · spec Prf3 · Paper 2 style · ★★☆

A student notices that \(1 + 2 = 3\), \(4 + 5 + 6 = 7 + 8\), \(9 + 10 + 11 + 12 = 13 + 14 + 15\) and conjectures that the pattern continues. Which of the following describes the \(n\)th line of the pattern?

AThe \(n\)th line starts at \(n^2\) and has \(n + 1\) numbers on the left and \(n\) on the right.
BThe \(n\)th line starts at \(n(n+1)\) and has \(n + 1\) numbers on the left.
CThe \(n\)th line starts at \(n^2\) and has \(n\) numbers on the left and \(n + 1\) on the right.
DThe \(n\)th line starts at \(n^2\) and has \(n\) numbers on each side.
EThe \(n\)th line starts at \(2n - 1\) and has \(n + 1\) numbers on the left.

Answer: A. Line \(1\) starts at \(1\), line \(2\) at \(4\), line \(3\) at \(9\): start \(n^2\). Left sides have \(2, 3, 4\) numbers (\(n + 1\)), right sides \(1, 2, 3\) (\(n\)).

Full method — how and why

Describing a pattern precisely: check the start value and the two counts separately against every given line.

Starting values: \(1, 4, 9\) for lines \(1, 2, 3\) - these are \(n^2\).
Test against all three lines, not just one.
Count the left sides: \(\{1,2\}\), \(\{4,5,6\}\), \(\{9,10,11,12\}\) - that is \(2, 3, 4\) terms, i.e. \(n+1\).
Count carefully; being off by one here is the whole point of the question.
Count the right sides: \(\{3\}\), \(\{7,8\}\), \(\{13,14,15\}\) - that is \(1, 2, 3\) terms, i.e. \(n\).
Left has one more term than right, which is what makes the equality possible (the right-hand terms are larger).
So: starts at \(n^2\), with \(n+1\) terms on the left and \(n\) on the right.
Check the total count: \((n+1) + n = 2n+1\), and indeed line \(3\) runs from \(9\) to \(15\), seven numbers ✓.

Where it goes wrong

Swapping the counts (\(n\) left, \(n+1\) right) - the sides would not balance, since the right-hand numbers are bigger.
Reading the start as \(2n-1\) or \(n(n+1)\) - both fail at line \(2\) (\(3\) and \(6\) rather than \(4\)).

Takeaway Verify a conjectured pattern against every given line, and check each component (start, length) separately.

18. PRF-12Mathematical proof · spec Prf2 · Paper 2 style · ★★☆

For a positive integer \(n\) it is known that: (i) if \(n\) is a multiple of \(4\) then \(n\) is not a multiple of \(6\); (ii) \(n\) is a multiple of \(12\) or \(n\) is a multiple of \(4\). What can be deduced?

AThe premises are inconsistent unless \(n\) is a multiple of \(4\) but not of \(6\); in particular \(n\) cannot be a multiple of \(12\).
B\(n\) is not a multiple of \(4\).
C\(n\) is a multiple of \(12\).
D\(n\) is a multiple of \(6\).
ENothing can be deduced.

Answer: A. If \(n\) were a multiple of \(12\) it would be a multiple of both \(4\) and \(6\), contradicting (i). So by (ii) \(n\) is a multiple of \(4\), and by (i) not a multiple of \(6\).

Full method — how and why

Deduction from two premises. Test the strongest-looking option against premise (i) first.

Suppose \(n\) were a multiple of \(12\). Then \(12 = 4\times3\) and \(12 = 6 \times 2\), so \(n\) is a multiple of both \(4\) and \(6\).
Exploring the tempting case first often resolves the whole question.
But (i) says a multiple of \(4\) is not a multiple of \(6\) - contradiction. So \(n\) is not a multiple of \(12\).
A supposition leading to a contradiction is ruled out.
Premise (ii) offers two alternatives and the first is now impossible, so \(n\) must be a multiple of \(4\).
Disjunctive syllogism: '\(A\) or \(B\)' plus 'not \(A\)' gives \(B\).
Then (i) applies: \(n\) is a multiple of \(4\) but not of \(6\).
That is the full deduction.

Where it goes wrong

Concluding \(n\) is a multiple of \(12\) by picking the first branch of (ii) without testing it.
Declaring the premises inconsistent - they are perfectly consistent (e.g. \(n = 4\) or \(n = 8\)).
Concluding nothing, missing that one branch of the 'or' is eliminated.

Takeaway With 'A or B', eliminate one branch and the other must hold; always test the branch that clashes with the other premise.

19. PRF-15Mathematical proof · spec Prf3 · Paper 2 style · ★★☆

Let \(u_n = n^2 - n + 41\). Which of the following statements is/are true?

I\(u_n\) is prime for \(n = 1, 2, 3, 4, 5\).
II\(u_n\) is prime for all positive integers \(n\).
III\(u_{41}\) is divisible by \(41\).

Anone of them
BI only
CII only
DIII only
EI and II only
FI and III only
GII and III only
HI, II and III

Answer: F. \(u_1 = 41\), \(u_2 = 43\), \(u_3 = 47\), \(u_4 = 53\), \(u_5 = 61\): all prime (I). \(u_{41} = 41^2 - 41 + 41 = 41^2\), divisible by \(41\) (III) and not prime, so II is false - small cases do not prove a general claim.

Full method — how and why

The classic warning about pattern-spotting: a formula can produce primes for many values and still fail.

I: compute \(u_1 = 41\), \(u_2 = 4-2+41 = 43\), \(u_3 = 9-3+41=47\), \(u_4 = 16-4+41 = 53\), \(u_5 = 25-5+41=61\). All prime. True.
Straight substitution; all five are primes (none divisible by \(2,3,5\) and each is below \(64\) or checkable quickly).
III: \(u_{41} = 41^2 - 41 + 41 = 41^2\). Divisible by \(41\). True.
The \(-41\) and \(+41\) cancel exactly - which is why \(n = 41\) is the natural place to look for failure.
II: since \(u_{41} = 41^2 = 1681\) has factor \(41\), it is not prime. False.
One counterexample kills the universal claim, however many earlier cases worked.
So I and III.
Match to the list.

Where it goes wrong

Accepting II because the first several values are prime - this formula is famous precisely because it works for \(n = 1\) to \(40\) and then fails.
Trying to check \(u_{41}\) by multiplying out \(1681\) instead of spotting the cancellation.

Takeaway Many confirming cases never prove a universal claim; and when hunting for failure, look for the value that makes terms cancel.

20. PRF-18Mathematical proof · spec Prf2 · Paper 2 style · ★★☆

Every element of a set \(S\) of integers is either a multiple of \(3\) or a multiple of \(5\). Every multiple of \(3\) in \(S\) is negative. \(S\) contains the number \(10\). Which of the following statements must be true?

I\(S\) contains a positive multiple of \(5\).
II\(S\) contains no positive multiple of \(3\).
III\(S\) contains a negative number.

Anone of them
BI only
CII only
DIII only
EI and II only
FI and III only
GII and III only
HI, II and III

Answer: E. \(10 \in S\) is a positive multiple of \(5\) (I). Multiples of \(3\) in \(S\) are negative, so none is positive (II). III fails: \(S = \{10\}\) satisfies everything.

Full method — how and why

'Must be true' with a concrete object given. Some claims follow from the given element; others need a counterexample set.

I: \(10 \in S\) and \(10 = 2 \times 5\) is a positive multiple of \(5\). Must be true.
The element is handed to you; nothing more is needed.
II: the second condition says every multiple of \(3\) in \(S\) is negative, so none can be positive. Must be true.
Note this is vacuously fine even if \(S\) contains no multiples of \(3\) at all.
III: must \(S\) contain a negative number? Try \(S = \{10\}\): every element is a multiple of \(3\) or \(5\) ✓, there are no multiples of \(3\) to be negative ✓, and \(10 \in S\) ✓. No negative number. Not necessarily true.
A single valid \(S\) with no negative element refutes 'must be true'.
So I and II.
Match to the list.

Where it goes wrong

Reading 'every multiple of \(3\) in \(S\) is negative' as promising that \(S\) has a multiple of \(3\) - a universal statement can be true with nothing to apply it to.
Confusing 'could be true' with 'must be true' for III.

Takeaway A conditional statement about members of a set is vacuously true when no member qualifies; to refute 'must be true', build a legal example that fails it.

21. PRF-19Mathematical proof · spec Prf1 · Paper 2 style · ★★☆

A student proves that \(\sqrt{4}\) is irrational by copying the standard proof for \(\sqrt2\): 'Suppose \(\sqrt4 = p/q\) in lowest terms; then \(p^2 = 4q^2\), so \(p^2\) is even, so \(p\) is even, \(p = 2k\); then \(4k^2 = 4q^2\), so \(k^2 = q^2\)...' At which point does the argument break down compared with the \(\sqrt2\) proof?

A\(\sqrt4\) cannot be written as \(p/q\).
B\(p^2 = 4q^2\) does not imply that \(p\) is even.
C\(k^2 = q^2\) does not show that \(q\) is even, so no contradiction arises.
DIt is not valid to assume \(p\) and \(q\) have no common factor.
EThe argument is valid, so \(\sqrt4\) is irrational.

Answer: C. For \(\sqrt2\) the step \(p^2 = 2q^2\) leads to \(2k^2 = q^2\), making \(q\) even. Here \(k^2 = q^2\) carries no parity information, so the contradiction never appears - as expected since \(\sqrt4 = 2\).

Full method — how and why

Diagnosing why a proof technique fails when transplanted. Follow the argument line by line and find the step that no longer bites.

Suppose \(\sqrt4 = \frac pq\) in lowest terms; then \(p^2 = 4q^2\), so \(p^2\) is even, so \(p\) is even - this much is fine.
\(4q^2\) is certainly even, and an odd number squared is odd, so \(p\) must be even.
Substituting \(p = 2k\): \(4k^2 = 4q^2\), i.e. \(k^2 = q^2\).
Here the \(4\) cancels entirely, because the constant was \(4\) and not \(2\).
Compare with \(\sqrt2\): there \(p^2 = 2q^2\) gives \(4k^2 = 2q^2\), i.e. \(q^2 = 2k^2\) - a spare factor of \(2\) forcing \(q\) even.
That leftover factor of \(2\) is the whole engine of the classical proof.
With \(\sqrt4\) no factor is left over, so \(k^2 = q^2\) tells you nothing about the parity of \(q\), and no contradiction ever appears.
Correctly so: \(\sqrt4 = 2\) is rational, so no proof of irrationality could possibly succeed.

Where it goes wrong

Claiming \(p^2 = 4q^2\) fails to make \(p\) even - it does not fail; that step is valid.
Claiming the 'lowest terms' assumption is illegitimate - every rational can be written that way.
Accepting the argument and concluding \(\sqrt4\) is irrational, when \(\sqrt4 = 2\).

Takeaway The \(\sqrt2\) proof works because \(2\) is prime; the leftover prime factor is what forces the second parity. Check where an adapted proof loses its engine.

Mathematical proof — solutions