Further Proof Techniques

Proof is the heartbeat of mathematics: the discipline of establishing a statement beyond any doubt, by pure logic from agreed truths. A-Level Maths introduces direct proof, proof by exhaustion and disproof by counterexample; Further Mathematics adds the two most powerful weapons — proof by contradiction and proof by contrapositive — and demands genuine rigour in writing them. These are the techniques that prove $\sqrt2$2​ is irrational, that there are infinitely many primes, and a host of results no amount of checking examples could ever settle.

This lesson treats each method as a precise logical structure, not a recipe to mimic: what you assume, what you must derive, and how you conclude. We work the classic proofs with examiner commentary, consolidate proof by induction (covered fully earlier in this course), and drill the meta-skill that exam questions really test — choosing the right method and writing it with watertight logic.

---

Where this sits in AQA 7367

This is the proof strand of the compulsory pure content examined on Paper 1 and Paper 2 (each 2 hours, 100 marks, 33⅓% of the A-Level), and proof threads through every topic. It extends the A-Level Maths proof toolkit (direct, exhaustion, counterexample, the introduction to contradiction) with full proof by contradiction and contrapositive, and consolidates induction. Proof is overwhelmingly AO2 — constructing a rigorous, well-communicated argument — and the rigour of your writing (clear assumptions, logical flow, explicit conclusion) is assessed as much as the idea.

---

Core theory: the four logical structures

Every proof method is a fixed logical template. Knowing the template tells you exactly what to assume and what to establish.

Direct proof

Assume the hypotheses and deduce the conclusion by a chain of valid steps: $P \implies \cdots \implies Q$P⟹⋯⟹Q. Best when the implication is "forward-flowing".

Example. The sum of two consecutive integers is odd. Let them be $n$n and $n+1$n+1; then $n+(n+1) = 2n+1$n+(n+1)=2n+1, which is odd by definition. $\blacksquare$■

Proof by contradiction (reductio ad absurdum)

To prove $P$P, assume $\neg P$¬P (the negation) and derive a logical impossibility. Since the negation forces an absurdity, $P$P must be true. This is the tool of choice for proving irrationality, non-existence, and "there is no largest …" statements — anywhere the negation is more concrete to work with than the statement itself. The power of the method is that the negation often hands you something specific to manipulate: "assume $\sqrt2$2​ is rational" gives you an actual fraction $\tfrac{a}{b}$ba​ to square; "assume finitely many primes" gives you a finite list to multiply together. The art lies in choosing what to do with that concrete object so that an unavoidable contradiction emerges — typically a quantity that is forced to be two incompatible things at once (even and odd; in the list and not in the list; a common factor where there should be none).

Proof by contrapositive

The contrapositive of "$P \implies Q$P⟹Q" is "$\neg Q \implies \neg P$¬Q⟹¬P", and the two are logically equivalent (identical truth tables). When the converse-direction "$\neg Q \implies \neg P$¬Q⟹¬P" is easier to handle than the original, prove that instead. Especially powerful for statements about $n$n where assuming "$n$n is odd" (i.e. $\neg Q$¬Q) gives a concrete $n=2k+1$n=2k+1 to compute with. The classic signal that the contrapositive will help is a statement of the form "if [something about $n^2$n2 or $n^3$n3] then [something about $n$n]": going forwards forces you to extract information about $n$n from $n^2$n2 (awkward, since square-rooting loses sign and parity), whereas the contrapositive lets you start from a clean $n = 2k+1$n=2k+1 and compute $n^2$n2 directly. Beware the common confusion with the converse "$Q \implies P$Q⟹P": the converse is not equivalent to the original, whereas the contrapositive is — mixing them up is a fatal logical error.

Proof by exhaustion and disproof by counterexample

Exhaustion splits the claim into finitely many cases and verifies each — legitimate only when the cases are genuinely exhaustive and finite (e.g. "$n$n even or $n$n odd", or the residues $n\equiv 0,1,2 \pmod 3$n≡0,1,2(mod3)). The two obligations are that the cases be mutually exhaustive (every possibility falls into at least one) and that each case be verified; a top answer states explicitly that the cases cover all possibilities, since an incomplete case split is a silent gap. Counterexample is the asymmetry at the heart of logic: a universal statement "$\forall n,\ P(n)$∀n, P(n)" is disproved by a single $n$n with $\neg P(n)$¬P(n) — one exception is fatal, whereas no number of confirming examples ever proves a universal. This asymmetry is not a quirk but a direct consequence of the meaning of the quantifiers: "for all" is falsified by "there exists a counterexample", while "there exists" is established by a single witness. Internalising this saves you from the commonest beginner's error — believing that checking the first few cases of a pattern constitutes a proof.

The contradiction/contrapositive distinction. Both start by negating something, which causes confusion. In contrapositive you assume only $\neg Q$¬Q and derive $\neg P$¬P — a self-contained direct proof of an equivalent statement. In contradiction you assume the entire statement is false (for "$P\implies Q$P⟹Q" that means $P\ \text{and}\ \neg Q$P and ¬Q) and derive any absurdity. Contrapositive is cleaner when it applies; contradiction is more general.

---

Worked examples (with mark scheme)

Example 1 — irrationality of $\sqrt2$2​ (contradiction)

Prove that $\sqrt2$2​ is irrational.

Assume the negation: suppose $\sqrt2$2​ is rational, so $\sqrt2 = \dfrac{a}{b}$2​=ba​ with $a,b\in\mathbb{Z}$a,b∈Z, $b\neq0$b=0, and the fraction in lowest terms (no common factor). (M1: correct assumption + "lowest terms")

Square and rearrange:

$2 = \frac{a^2}{b^2} \;\Rightarrow\; a^2 = 2b^2. \quad (\text{M1})$2=b2a2​⇒a2=2b2.(M1)

So $a^2$a2 is even, hence $a$a is even (by the contrapositive result of Example 2). Write $a = 2k$a=2k:

$(2k)^2 = 2b^2 \;\Rightarrow\; 4k^2 = 2b^2 \;\Rightarrow\; b^2 = 2k^2. \quad (\text{M1})$(2k)2=2b2⇒4k2=2b2⇒b2=2k2.(M1)

So $b^2$b2 is even, hence $b$b is even. But then $a$a and $b$b share the factor 2 — contradicting "lowest terms". (A1: identify the contradiction)

Therefore $\sqrt2$2​ is irrational. $\blacksquare$■ (A1: conclude)

(M1 assumption stated with "no common factor"; M1 reach $a^2=2b^2$a2=2b2; M1 deduce both even; A1 the contradiction with coprimality; A1 explicit conclusion. The "lowest terms" assumption is essential — it is the thing contradicted; omit it and the proof collapses.)

Example 2 — "$n^2$n2 even $\Rightarrow n$⇒n even" (contrapositive)

Prove: if $n^2$n2 is even then $n$n is even.

A direct attack is awkward (you would factor $n^2$n2). The contrapositive is "if $n$n is odd then $n^2$n2 is odd", which gives a concrete $n$n to compute. (M1: state the contrapositive)

Let $n = 2k+1$n=2k+1. Then

$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, \quad (\text{M1})$n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1,(M1)

which is odd. (A1) Since the contrapositive is true, so is the original statement. $\blacksquare$■ (A1: link back)

(M1 correctly state the contrapositive; M1 expand $(2k+1)^2$(2k+1)2; A1 conclude $n^2$n2 odd; A1 the crucial "hence the original holds". Forgetting that final link — treating the contrapositive proof as if it were the original — is a common lost mark.)

Example 3 — infinitely many primes (contradiction)

Prove there are infinitely many primes.

Assume the negation: suppose there are only finitely many primes, $p_1, p_2, \ldots, p_n$p1​,p2​,…,pn​. (M1) Consider

$N = p_1 p_2 \cdots p_n + 1. \quad (\text{M1: the construction})$N=p1​p2​⋯pn​+1.(M1: the construction)

Now $N > 1$N>1, so $N$N has at least one prime factor $p$p. But dividing $N$N by any $p_i$pi​ leaves remainder $1$1, so $p \neq p_i$p=pi​ for every $i$i — a prime not in the list. (A1) This contradicts the assumption that $p_1,\ldots,p_n$p1​,…,pn​ were all the primes. Hence there are infinitely many primes. $\blacksquare$■ (A1)

(M1 assume finitely many; M1 the key construction $N = \prod p_i + 1$N=∏pi​+1; A1 the "remainder 1, so a new prime" argument; A1 contradiction + conclusion. The construction is the whole idea — note we do not claim $N$N itself is prime, only that its prime factor is new.)

Example 4 — proof by exhaustion

Prove that $n^2 + n$n2+n is even for every integer $n$n.

Every integer is either even or odd, so two exhaustive cases cover all possibilities. (M1: set up the two cases)

Case 1 ($n$n even): write $n = 2k$n=2k. Then $n^2 + n = 4k^2 + 2k = 2(2k^2 + k)$n2+n=4k2+2k=2(2k2+k), which is even. (A1)

Case 2 ($n$n odd): write $n = 2k+1$n=2k+1. Then

$n^2 + n = (2k+1)^2 + (2k+1) = 4k^2 + 4k + 1 + 2k + 1 = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1),$n2+n=(2k+1)2+(2k+1)=4k2+4k+1+2k+1=4k2+6k+2=2(2k2+3k+1),

which is even. (A1)

Both cases give an even result, and they exhaust all integers, so $n^2 + n$n2+n is even for every integer $n$n. $\blacksquare$■ (A1: state cases are exhaustive)

(M1 the two-case split; A1 each case; A1 the explicit "the cases are exhaustive" closure. Note the slicker direct alternative: $n^2 + n = n(n+1)$n2+n=n(n+1) is a product of two consecutive integers, one of which must be even — a one-line proof that a top candidate might offer alongside the exhaustion. Showing you can do it both ways demonstrates command of method choice.)

---

Specimen-style exam question

(specimen-style — not from any past paper)

(a) Prove by contradiction that if $n^2$n2 is a multiple of $3$3, then $n$n is a multiple of $3$3. (b) Hence prove by contradiction that $\sqrt3$3​ is irrational.

(a) Suppose, for contradiction, that $n^2$n2 is a multiple of $3$3 but $n$n is not. Then $n \equiv 1$n≡1 or $n \equiv 2 \pmod 3$n≡2(mod3), i.e. $n = 3k+1$n=3k+1 or $n = 3k+2$n=3k+2. Squaring: $(3k+1)^2 = 9k^2+6k+1 = 3(3k^2+2k)+1$(3k+1)2=9k2+6k+1=3(3k2+2k)+1, and $(3k+2)^2 = 9k^2+12k+4 = 3(3k^2+4k+1)+1$(3k+2)2=9k2+12k+4=3(3k2+4k+1)+1. In both cases $n^2 \equiv 1 \pmod 3$n2≡1(mod3), so $n^2$n2 is not a multiple of $3$3 — contradicting the hypothesis. Hence $n$n is a multiple of $3$3. $\blacksquare$■

(b) Suppose $\sqrt3$3​ is rational: $\sqrt3 = \tfrac{a}{b}$3​=ba​ in lowest terms. Then $a^2 = 3b^2$a2=3b2, so $a^2$a2 is a multiple of $3$3; by part (a), $a$a is a multiple of $3$3, say $a = 3k$a=3k. Then $9k^2 = 3b^2 \Rightarrow b^2 = 3k^2$9k2=3b2⇒b2=3k2, so $b^2$b2 and hence $b$b is a multiple of $3$3. Now $a$a and $b$b share the factor $3$3, contradicting "lowest terms". Therefore $\sqrt3$3​ is irrational. $\blacksquare$■

The structure rewards precision in two places. First, part (a)'s case analysis must cover all non-multiples of 3 — both $3k+1$3k+1 and $3k+2$3k+2 — and a top answer notes this is itself a small proof by exhaustion. Second, part (b) is a textbook "hence": it uses part (a) as a lemma at exactly the step "$a^2$a2 a multiple of 3 $\Rightarrow a$⇒a a multiple of 3", rather than re-deriving it. Spotting that the irrationality of $\sqrt3$3​ needs the $\sqrt3$3​-analogue of "even $\Rightarrow$⇒ even" — and that this analogue is precisely part (a) — is the synoptic insight the examiner is probing. (The same scaffold proves $\sqrt p$p​ irrational for any prime $p$p.)

---

Synoptic links