Lesson 1: Algebraic Methods — Proof

A-level mathematics begins where GCSE ends: with proof. At GCSE you learned techniques; at A-level you must justify them. Why does the quadratic formula work? Why is the sum of two odd numbers always even? Proof turns mathematics from a collection of recipes into a logical structure where every claim is earned. This lesson introduces the four proof methods examined at A-level — deduction, exhaustion, contradiction, and counter-example — alongside the algebraic fluency (algebraic fractions, the binomial theorem) that proof problems demand. Proof appears in every A-level paper, and examiners award marks for logical structure as well as correct algebra.

What counts as proof?

A proof is a watertight logical argument that establishes a statement for every case it claims to cover. Testing a thousand examples is not proof — the thousand-and-first could break the pattern. Consider the famous near-miss: n² + n + 41 is prime for n = 0, 1, 2, ..., 39 (try n = 0: 41, prime; n = 1: 43, prime; n = 2: 47, prime...), but at n = 40 it equals 40² + 40 + 41 = 40(40 + 1) + 41 = 41 × 41 = 1681, which is not prime. Forty correct examples proved nothing. A-level examiners test this understanding directly: 'prove' means deduce, not demonstrate.

Mathematical statements come in flavours. A conjecture is an unproven claim (Goldbach's conjecture — every even number above 2 is the sum of two primes — has resisted proof since 1742). A theorem is a proven statement; a lemma is a small theorem used as a stepping stone; a corollary follows easily from a theorem. At A-level you will prove modest but genuine theorems, and the discipline you build — stating assumptions, chaining implications, concluding cleanly — is the single most transferable skill in the course.

Proof by deduction is the workhorse: start from known facts and derive the conclusion step by step. Example: prove that the sum of two odd numbers is even. Let the odd numbers be 2m + 1 and 2n + 1 (every odd number has this form — this is the crucial definitional step). Their sum is 2m + 1 + 2n + 1 = 2(m + n + 1), which is twice an integer, hence even. QED. Notice the structure: define, manipulate, conclude. Every deduction proof follows this skeleton.

Worked example (deduction). Prove that the difference between the squares of two consecutive integers is always odd. Let the integers be n and n + 1. Then (n + 1)² − n² = n² + 2n + 1 − n² = 2n + 1. Since 2n is even, 2n + 1 is odd for every integer n. ∎ The same skeleton works: define with algebra, expand, and read off the conclusion from the form of the final expression — a multiple of 2 plus 1 can only be odd.

Proof by exhaustion

Proof by exhaustion checks every possible case — feasible only when the cases are few. Example: prove that n² + n is even for every integer n. There are exactly two cases: n even or n odd. If n = 2k, then n² + n = 4k² + 2k = 2(2k² + k), even. If n = 2k + 1, then n² + n = (4k² + 4k + 1) + (2k + 1) = 4k² + 6k + 2 = 2(2k² + 3k + 1), even. Both cases give an even result, so the statement holds for all integers. The phrase 'in all cases' is the signal that exhaustion is complete.

Exhaustion suits problems about remainders and digits. Example: prove that the square of any integer leaves remainder 0 or 1 when divided by 4. Cases: n = 2k gives n² = 4k² (remainder 0); n = 2k + 1 gives n² = 4k² + 4k + 1 = 4(k² + k) + 1 (remainder 1). Done. Examiners love remainder problems because they force case discipline — missing a case loses the proof mark.

The limitation is obvious: you cannot exhaust infinitely many cases. Nobody can check every integer. Exhaustion works for parity (2 cases), remainders modulo m (m cases), or digits (10 cases). When a problem says 'for all integers n', think contradiction or deduction; when it says 'for all digits' or gives a small modulus, exhaustion is likely the intended method.

Proof by contradiction

Proof by contradiction assumes the opposite of what you want to prove, then derives an absurdity. The classic: prove that √2 is irrational. Suppose, for contradiction, that √2 = a/b in lowest terms (a, b integers, no common factor). Then 2 = a²/b², so a² = 2b² — meaning a² is even, so a is even (the square of an odd number is odd). Write a = 2k: then 4k² = 2b², so b² = 2k², and b is even too. But a and b both even contradicts 'lowest terms'. Therefore our assumption was false: √2 is irrational. This argument, over two thousand years old, remains the model contradiction proof.

The structure is rigid and examiners check it: (1) state the assumption clearly ('assume, for contradiction, that...'); (2) derive consequences using valid algebra; (3) identify the contradiction explicitly ('this contradicts...'); (4) conclude ('therefore...'). Marks are lost for vague contradictions — you must name exactly what is contradicted. A favourite A-level application: prove there are infinitely many primes. Assume finitely many, p₁, ..., pₙ; consider N = p₁p₂...pₙ + 1; N has a prime factor, but it cannot be any listed prime (each leaves remainder 1 when divided into N), contradiction. Hence infinitely many primes — Euclid's proof, still examined.

Contradiction also proves impossibility results: there is no largest integer (assume N is largest; N + 1 is larger, contradiction), and no rational number squares to 3 (same structure as √2). When a problem asks you to prove something is impossible, or that something 'cannot' happen, contradiction is almost always the method.

Disproof by counter-example

To disprove a universal statement ('for all x...'), a single counter-example suffices — one black swan refutes 'all swans are white'. Example: disprove 'if n is prime then n² + 2 is prime'. Take n = 3 (prime): 3² + 2 = 11, prime — not a counter-example. Take n = 5: 25 + 2 = 27 = 3 × 9, not prime. One counter-example disproves the claim. The art is in the search: test small cases systematically.

Counter-examples must genuinely satisfy the hypothesis. To disprove 'all numbers of the form 2ⁿ − 1 are prime' (Mersenne's claim), n = 4 gives 2⁴ − 1 = 15, composite — but the hypothesis only covered prime n, so n = 4 does not count. The valid counter-example is n = 11: 2¹¹ − 1 = 2047 = 23 × 89. Examiners set traps here: they give statements with subtle hypotheses, and the counter-example must meet every condition.

Note the asymmetry: examples can disprove but never prove a universal claim. This is why the lesson's opening example (n² + n + 41) matters so much. In your exam answers, never write 'true for n = 1, 2, 3, therefore true for all n' — that earns zero proof marks and signals a fundamental misunderstanding.

Algebraic fluency for proof — fractions and the binomial theorem

Proof problems demand flawless algebra, especially algebraic fractions. Simplify (x² − 9)/(x² + 6x + 9) ÷ (x − 3)/(x + 3): factorise everything first — (x − 3)(x + 3)/(x + 3)² × (x + 3)/(x − 3) — then cancel: the (x − 3) terms cancel, and (x + 3)² in the denominator cancels with the two (x + 3) factors in the numerators, leaving 1. Factorise before cancelling, never cancel across a sum, and state restrictions (x ≠ ±3). Division by zero invalidates proof steps silently.

The binomial theorem — (a + b)ⁿ = Σ C(n, r) aⁿ⁻ʳ bʳ — is itself proved by a beautiful argument (counting how each term of the expansion picks a's and b's), and it generates proof exercises. Example: prove that (1 + x)ⁿ ≥ 1 + nx for x > −1 (Bernoulli's inequality) — expand and note all further terms are non-negative. Or prove Σ C(n, r) = 2ⁿ by setting a = b = 1. Worked expansion: (2 − x)⁴ = C(4,0)2⁴ − C(4,1)2³x + C(4,2)2²x² − C(4,3)2x³ + C(4,4)x⁴ = 16 − 32x + 24x² − 8x³ + x⁴.

Partial fractions complete the toolkit: write (3x + 5)/((x + 1)(x + 2)) as A/(x + 1) + B/(x + 2). Then 3x + 5 = A(x + 2) + B(x + 1); set x = −1: 2 = A; set x = −2: −1 = −B, so B = 1. Partial fractions turn hard integrals and series into easy ones — they repay the effort many times over in Lessons 6 and 11.

Common mistakes

• Proving by example. Checking n = 1, 2, 3 and concluding 'true for all n' scores zero — examiners list this as the most common proof error every year.
• Assuming the conclusion. Starting from what you want to prove and working backwards to something true, without reversible steps, is circular. Work forwards from definitions, or state clearly why each step reverses.
• A counter-example that breaks the hypothesis. If the claim is about prime n, an even n proves nothing. Check your counter-example satisfies every condition in the statement.
• Vague contradictions. '...which is a contradiction' without saying what is contradicted (lowest terms? the assumption of finiteness?) loses the final mark. Name it.
• Cancelling across sums in algebraic fractions. (x + 3)/(x + 5) does not simplify. Factorise numerator and denominator completely first, and state excluded values.

Exam Experience

Questions in the style of the A-level pure paper. Attempt them before reading the mark scheme.

1. By giving a counter-example, disprove the statement: 'For all real numbers x, if x² > 4 then x > 2.' [2]

2. Prove that the sum of three consecutive integers is divisible by 3. [3]

3. Prove, by exhaustion, that n³ − n is divisible by 3 for every integer n. [4]

Mark scheme.

• 1. Choose a value with x² > 4 but x ≤ 2, e.g. x = −3 (M1). Then x² = 9 > 4 but −3 is not greater than 2, so the statement is false (A1). Any x < −2 earns the marks; x = −2 does not (x² = 4 fails the hypothesis).
• 2. Let the integers be n, n + 1, n + 2 (M1) for defining a general case rather than examples. Sum = 3n + 3 (M1). = 3(n + 1), a multiple of 3, hence divisible by 3 (A1) — the final factorised form is what displays divisibility.
• 3. Every integer is of the form 3k, 3k + 1 or 3k + 2 (M1) for the complete case split. Case n = 3k: n³ − n = 27k³ − 3k = 3(9k³ − k) (A1). Case n = 3k + 1: n³ − n = 27k³ + 27k² + 9k + 1 − 3k − 1 = 27k³ + 27k² + 6k = 3(9k³ + 9k² + 2k) (A1). Case n = 3k + 2: n³ − n = 27k³ + 54k² + 36k + 8 − 3k − 2 = 27k³ + 54k² + 33k + 6 = 3(9k³ + 18k² + 11k + 2); all cases give a multiple of 3, so the statement holds for every integer n (A1).