Proof by induction
Base case (n=1): show statement true. Inductive step: assume true for k, prove for k+1.
Proof by induction is mandatory FM technique. Used for sums, divisibility, matrices, sequences. Always state both steps; weak versions deduct marks.
Worked examples
1 + 2 + ... + n = n(n+1)/2. Base n=1: 1 = 1. Step: assume true for k; for k+1 add (k+1) and simplify.
2n > n for all n ≥ 1. Base: 2 > 1. Step: 2k+1 = 2 × 2k > 2k > k+1 (for k ≥ 1).
Divisibility: 7n − 1 divisible by 6.
Frequently asked questions
Strong induction?
Assume true for ALL values up to k, prove for k+1. Used when k+1 case requires multiple previous cases.
Why does induction work?
Domino effect. Base case + each step implies the next gives all positive integers.