A-Level Maths proof: deduction, exhaustion, counter-example and contradiction

Where proof sits in each specification

The key ideas

Proof by deduction starts from definitions and known results and moves forward. Use algebra to represent general numbers: an even number is 2n, an odd number is 2n + 1, consecutive integers are n, n + 1, n + 2. Checking a few examples is never a proof, because it does not cover every case.

Proof by exhaustion splits the situation into a finite set of cases that together cover everything, then proves each one. Typical splits are odd and even, or n = 3m, 3m + 1, 3m + 2. Disproof by counter-example needs only one case where the statement fails, clearly shown.

Proof by contradiction assumes the opposite of what you want to prove and shows that this leads to something impossible. The structure is fixed: state the assumption, reason from it, reach a contradiction, then conclude that the assumption was false and so the original statement is true.

Worked example 1 (deduction and exhaustion): prove that the square of any integer is of the form 3k or 3k + 1

1. Every integer n can be written as 3m, 3m + 1 or 3m + 2 for some integer m. These three cases cover all integers.
2. Case 1: (3m)^2 = 9m^2 = 3(3m^2), which is of the form 3k.
3. Case 2: (3m + 1)^2 = 9m^2 + 6m + 1 = 3(3m^2 + 2m) + 1, which is of the form 3k + 1.
4. Case 3: (3m + 2)^2 = 9m^2 + 12m + 4 = 3(3m^2 + 4m + 1) + 1, which is of the form 3k + 1.
5. Conclusion: in every case n^2 is of the form 3k or 3k + 1, so the result is true for all integers.

Worked example 2 (contradiction, Edexcel P4): prove that sqrt2 is irrational

1. Assume the opposite: sqrt2 is rational, so sqrt2 = a/b where a and b are integers with no common factor and b is not 0.
2. Square both sides: 2 = a^2/b^2, so a^2 = 2b^2. So a^2 is even, which means a is even (the square of an odd number is odd).
3. Write a = 2c. Then 4c^2 = 2b^2, so b^2 = 2c^2, so b^2 is even and b is even.
4. Now a and b are both even, so they share the factor 2. This contradicts the assumption that they have no common factor.
5. Conclusion: the assumption is false, so sqrt2 is irrational.

Worked example 3 (counter-example): disprove 'n^2 - n + 1 is prime for every positive integer n'

1. Test values: n = 2 gives 3, n = 3 gives 7, n = 4 gives 13, all prime.
2. n = 5 gives 25 - 5 + 1 = 21 = 3 × 7, which is not prime.
3. Conclusion: n = 5 is a counter-example, so the statement is false. (n = 1 gives 1, which is also not prime.)

Common mistakes that cost marks

• Testing a few numbers and calling it a proof.
• Using the same letter for two different integers, such as writing two different odd numbers as 2n + 1 and 2n + 1.
• Not covering every case in a proof by exhaustion.
• In a contradiction proof, not stating the assumption clearly or not saying what it contradicts.
• Leaving out the concluding sentence. Examiners often reserve the final mark for it.
• In identity proofs (Cambridge and Edexcel), working on both sides at once or starting from the result.

Exam technique and how a tutor helps

Write proofs in full sentences linked by 'so', 'therefore' and 'which is'. Define your letters ('let n be an integer'), show every algebraic step, and end with a statement that repeats what has been proved. Proof questions are usually short in marks but strictly marked, so a clear layout matters as much as the idea.

Proof is the topic where students most need someone reading their writing. In one-to-one lessons a tutor marks the student's written proofs line by line against mark-scheme language, points out the missing justification or unclear step, and has the student rewrite until the argument is complete. A small bank of standard proofs (sqrt2, infinitely many primes, odd and even results) is then rehearsed until the structure is automatic.

Self-check: can you do these?

• Prove that the sum of any three consecutive integers is divisible by 3. (Hint: n + (n + 1) + (n + 2) = 3(n + 1))
• Prove that the product of two odd numbers is odd. (Hint: (2a + 1)(2b + 1) = 2(2ab + a + b) + 1)
• Find a counter-example to 'if n is prime, 2n + 1 is prime'. (Answer: n = 7 gives 15)
• Write the first line of a contradiction proof that there are infinitely many primes. (Answer: assume there are finitely many primes, p1, p2, ..., pn)
• Prove that (1 - cos 2x)/sin 2x ≡ tan x. (See the trigonometric identities page)