Proof by induction and contradiction · Year 13

In Year 13 you learn: proof by induction.

Proof is how mathematicians know a statement is true in every case, not just the ones they have tried. Proof by induction climbs an infinite ladder one rung at a time. Proof by contradiction shows the opposite is impossible. A single counterexample is enough to sink a false claim.

Key facts

• Induction: (1) prove the base case, usually n = 1. (2) Assume it is true for n = k. (3) Show it is then true for n = k + 1. (4) Conclude it is true for all n ≥ 1.
• For a sum, add the (k + 1)th term to the formula for k terms and simplify it into the formula with k + 1.
• For divisibility, write f(k + 1) in terms of f(k), for example by simplifying f(k + 1) − 5f(k).
• Standard sums: ∑ r = (n(n + 1))/2, ∑ r^2 = (n(n + 1)(2n + 1))/6, ∑ r^3 = ((n(n + 1))/2)^2.
• A counterexample is one case where a claim fails. Checking examples can disprove a claim but never proves a general one.

Worked examples