Proof techniques
A proof is an argument that leaves no case unchecked. The main tools are: direct proof (chain facts together), contradiction (assume the opposite and reach something impossible), the contrapositive (prove ‘not B implies not A’ instead of ‘A implies B’), induction (prove it for 1, then show each case gives the next) and construction (show something exists by building it).
Competition answers are often a number, but the reason the number is right is a proof: a bound plus an example, or a full list of cases.
When to try it
- The question says ‘prove’, ‘show that’, ‘find all’ or ‘for every’.
- You have found an answer and need to be sure there are no others.
- A statement is claimed for every whole number n.
Watch out: Checking examples is not a proof, and neither is an argument that only works for the cases you happened to try.
Worked example
Prove that the square of any odd number is one more than a multiple of 8.
Show the solution
- Write the odd number as 2k + 1. Then (2k + 1)² = 4k² + 4k + 1 = 4k(k + 1) + 1.
- k and k + 1 are consecutive, so one of them is even and k(k + 1) = 2m for a whole number m.
- So (2k + 1)² = 8m + 1.
Answer: (2k + 1)² = 8m + 1 for every whole number k
Practise: 55 problems that use proof techniques
- Junior (10): J36, J44, J53, J54, J58, J60, J104, J145 …
- Intermediate (13): I35, I41, I45, I53, I56, I60, I69, I80 …
- Senior (10): S35, S44, S47, S48, S117, S119, S51 (plan), S52 (plan) …
- Olympiad-style (22): O01 (plan), O02 (plan), O03 (plan), O06 (plan), O07 (plan), O08 (plan), O10 (plan), O14 (plan) …
Other strategies
Organised cases · Count the opposite · Working backwards · Invariants · Extremal principle · Pigeonhole principle · Parity and remainders · Symmetry · Spot the pattern and generalise