Mathematical Induction (DSE M2): How to Write the Proof
To prove a proposition P(n) for all positive integers n by mathematical induction: (1) show P(1) is true; (2) assume P(k) is true for some positive integer k and prove P(k + 1). Both steps and a concluding sentence are needed for full marks.
Why 1 + 3 + 5 + … + (2n − 1) = n²: each odd number adds an L-shaped border that grows a k × k square into a (k + 1) × (k + 1) square. This is the inductive step of Example 1 as a picture. Try it yourself →
Mathematical Induction: the Layout That Scores Full Marks
State the proposition. "Let P(n) be the proposition …"
Base case. "When n = 1, L.H.S. = …, R.H.S. = …". Compute both sides separately and state that P(1) is true.
Assumption. "Assume P(k) is true for some positive integer k, i.e. …". Write the formula with k in full.
Inductive step. "When n = k + 1, L.H.S. = (sum to k terms) + (the (k + 1)th term)". Replace the first part using the assumption, then factorise until it matches the R.H.S. with k + 1 in place of n.
Conclusion. "By the principle of mathematical induction, P(n) is true for all positive integers n."
Worked Examples — Mathematical Induction
Example 1: Sum of the first n odd numbers
Prove by mathematical induction that 1 + 3 + 5 + … + (2n − 1) = n² for all positive integers n.
When n = 1: L.H.S. = 1, R.H.S. = 1² = 1. So P(1) is true.
Assume P(k) is true: 1 + 3 + … + (2k − 1) = k² for some positive integer k.
When n = k + 1: L.H.S. = [1 + 3 + … + (2k − 1)] + (2k + 1)
= k² + 2k + 1 (by the assumption)
= (k + 1)² = R.H.S. So P(k + 1) is true.
Answer:By the principle of mathematical induction, P(n) is true for all positive integers n.
Example 2: A sum of products
Prove by mathematical induction that 1·2 + 2·3 + … + n(n + 1) = n(n + 1)(n + 2)/3 for all positive integers n.
When n = 1: L.H.S. = 2, R.H.S. = (1)(2)(3)/3 = 2. P(1) is true.
Assume 1·2 + … + k(k + 1) = k(k + 1)(k + 2)/3.
When n = k + 1: L.H.S. = k(k + 1)(k + 2)/3 + (k + 1)(k + 2)
Take out the common factor: = (k + 1)(k + 2)(k/3 + 1) = (k + 1)(k + 2)(k + 3)/3
This is the R.H.S. with n = k + 1, so P(k + 1) is true.
Answer:By the principle of mathematical induction, the proposition is true for all positive integers n.
💡 Exam Traps & Secrets
⚠️ Factorise, do not expandIn the inductive step, pull out the common factor straight away. Expanding everything into a cubic and trying to factorise it back is where most time and marks are lost.
⚠️ The assumption must actually be usedMark the line where you substitute the assumption ("by the assumption"). A proof of P(k + 1) that never uses P(k) is not an induction proof and loses the method marks.
⚠️ Do not start from what you want to proveStart from the L.H.S. and work towards the R.H.S. Writing "L.H.S. = R.H.S." first and manipulating both sides assumes the conclusion.
✏️ Self-Test: Quick Interactive Practice
How to study: Click any question below to instantly load it on the coordinate grid and check your steps.
(Sum of squares)Prove by mathematical induction that 1² + 2² + … + n² = n(n + 1)(2n + 1)/6.
(Sum of fractions)Prove by induction that 1/(1·2) + 1/(2·3) + … + 1/(n(n + 1)) = n/(n + 1).
(Sum with powers)Prove by induction that 1·2 + 2·2² + 3·2³ + … + n·2ⁿ = (n − 1)2ⁿ⁺¹ + 2.
Frequently Asked Questions
Two steps and a conclusion. Prove P(1) is true. Then assume P(k) is true for some positive integer k and prove P(k + 1). Conclude that P(n) is true for all positive integers n by the principle of mathematical induction.
No. The curriculum notes say induction proofs involving inequalities and divisibility are not required. M2 induction is about summation of finite sequences, and it can also appear with matrices or the binomial theorem.
Usually for missing wording: not stating P(1) is true, not saying "for some positive integer k", or leaving out the final sentence. Each of those lines carries a mark.