What is induction?
Induction proves a statement P(n) for all integers n ≥ some base value. You are not assuming P(k) is true — you are proving: if P(k) is true, then P(k+1) is true. Together with the base case (P true for the first value), that implies P(n) for all n ≥ base. Use k (not n) throughout the inductive step. Explicitly show the substitution in the base case and state obvious facts (e.g. 4 is divisible by 4).
Key points
- •Recipe: state P(n); check base case; assume P(k); prove P(k+1); conclude with the standard wording.
- •Conclusion: 'If P(k) is true then P(k+1) is true. P(base) is true. So P(n) is true for all integers n ≥ base.'
- •Derivatives: assume kth derivative, differentiate to get (k+1)th and match the proposition for n = k+1.
- •Divisibility: write expression for k+1 in terms of the assumed divisible expression; subtract a multiple to simplify.
- •Inequalities: apply an increasing function to both sides of P(k) to get toward P(k+1); each step must be iff.
- •Series: add the (k+1)th term to the sum and show it equals the formula with n = k+1.
Worked example
Prove 7ⁿ − 3ⁿ is divisible by 4 (positive integers n)
Prove that 7ⁿ − 3ⁿ is divisible by 4 for all positive integers n.
P(n): 7ⁿ − 3ⁿ divisible by 4. Base n=1: 7¹−3¹=4 ✓. Assume 7ᵏ−3ᵏ divisible by 4. Then 7ᵏ⁺¹−3ᵏ⁺¹ = 7·7ᵏ−3·3ᵏ. Subtract 3(7ᵏ−3ᵏ): still divisible by 4 iff 7·7ᵏ−3·3ᵏ−3(7ᵏ−3ᵏ)=4·7ᵏ is divisible by 4 ✓. Conclude.
Exam tips
- 💡Ensure you use the correct base case (not always 0 or 1). OCR uses 1 as the first natural number.
- 💡Write 'for integers n greater than or equal to [base]' in both the proposition and the conclusion.
- 💡Do not reuse n or k when defining new variables in the inductive step.
- 💡For divisibility, choose a convenient multiple of the assumed expression to subtract so a term cancels.
How Cambridge students approach this
How Cambridge students approach this: identify what 'going from k to k+1' means. For series, add one term. For derivatives, differentiate. For divisibility, express 7ᵏ⁺¹−3ᵏ⁺¹ and use the assumption. For inequalities, multiply both sides by (k+1) or apply another increasing function, then show the new inequality is equivalent to something trivially true.