Courses / Mathematics XI (HSSC-I) – FBISE Complete SLO-Based Course
7.1 The Principle of Mathematical Induction
Unit 7 – Mathematical Induction and Binomial Theorem · 60 min read · 18 MCQs to check yourself
Mathematical induction practice problems (The Organic Chemistry Tutor)
1. The domino idea
To prove a statement P(n) for all natural numbers n ≥ n₀:
| Step | What you show |
|---|---|
| 1. Base case | P(n₀) is true (usually n₀ = 1) |
| 2. Induction hypothesis | assume P(k) is true for some k ≥ n₀ |
| 3. Induction step | using the assumption, prove P(k + 1) is true |
| 4. Conclusion | by the principle of mathematical induction, P(n) is true for all n ≥ n₀ |
| Like a line of dominoes: the first falls (base case), and each falling domino knocks over the next (induction step), so all fall. |
2. Proving a summation formula
Prove 1 + 3 + 5 + … + (2n - 1) = n².
- Base case n = 1: LHS = 1, RHS = 1² = 1 ✓
- Hypothesis: 1 + 3 + … + (2k - 1) = k².
- Step: add the next term (2k + 1): k² + (2k + 1) = (k + 1)², which is P(k + 1) ✓
- Conclusion: true for all n ∈ N.
3. Proving divisibility
Prove 5ⁿ - 1 is divisible by 4 for all n ∈ N.
- n = 1: 5 - 1 = 4 ✓
- Assume 5^k - 1 = 4m for some integer m, i.e. 5^k = 4m + 1.
- Then 5^(k+1) - 1 = 5 · 5^k - 1 = 5(4m + 1) - 1 = 20m + 4 = 4(5m + 1) ✓ divisible by 4.
4. Proving an inequality
Prove 2ⁿ > n for all n ≥ 1. Base: 2 > 1 ✓. Assume 2^k > k. Then 2^(k+1) = 2 · 2^k > 2k = k + k ≥ k + 1 ✓. Statements that start later: n! > 2ⁿ is true only for n ≥ 4 (24 > 16), so the base case is n = 4.
5. Why both steps are needed
- n² - n + 41 is prime for n = 1, 2, …, 40 but not for n = 41 – checking cases is not a proof.
- "1 + 2 + … + n = (n(n + 1))/2 + 1" passes the induction step but fails the base case – so it is false.
Short and long questions
1. Prove by mathematical induction that 1 + 2 + 3 + … + n = (n(n + 1))/2 for all n ∈ N.
Model answer
Base case n = 1: LHS = 1, RHS = (1(2))/2 = 1 ✓ Hypothesis: assume 1 + 2 + … + k = (k(k + 1))/2. Step: 1 + 2 + … + k + (k + 1) = (k(k + 1))/2 + (k + 1) = ((k + 1)(k + 2))/2, which is the formula for n = k + 1 ✓ Conclusion: by the principle of mathematical induction the formula is true for all n ∈ N.
2. Prove by induction that n³ - n is divisible by 6 for all n ∈ N.
Model answer
Base n = 1: 1 - 1 = 0 = 6(0) ✓ Hypothesis: k³ - k = 6m. Step: (k + 1)³ - (k + 1) = k³ + 3k² + 3k + 1 - k - 1 = (k³ - k) + 3k(k + 1) = 6m + 3k(k + 1). k(k + 1) is a product of consecutive integers, so it is even; 3k(k + 1) is divisible by 6. Hence (k + 1)³ - (k + 1) is divisible by 6 ✓ Conclusion: true for all n ∈ N.
3. Prove by induction that 1² + 2² + … + n² = (n(n + 1)(2n + 1))/6.
Model answer
Base n = 1: 1 = (1 · 2 · 3)/6 ✓ Hypothesis: 1² + … + k² = (k(k + 1)(2k + 1))/6. Step: add (k + 1)²: (k(k + 1)(2k + 1) + 6(k + 1)²)/6 = ((k + 1)[2k² + k + 6k + 6])/6 = ((k + 1)(k + 2)(2k + 3))/6 – the formula for n = k + 1 ✓ Conclusion: true for all n ∈ N.
4. Prove by mathematical induction: (a) 1 · 2 + 2 · 3 + … + n(n + 1) = (n(n + 1)(n + 2))/3; (b) 4ⁿ - 1 is divisible by 3.
Model answer
(a) Base n = 1: 2 = (1 · 2 · 3)/3 ✓. Assume true for k. Add (k + 1)(k + 2): (k(k + 1)(k + 2))/3 + (k + 1)(k + 2) = ((k + 1)(k + 2)(k + 3))/3 ✓ – true for k + 1, hence for all n. (b) Base n = 1: 4 - 1 = 3 ✓. Assume 4^k - 1 = 3m. Then 4^(k+1) - 1 = 4 · 4^k - 1 = 4(3m + 1) - 1 = 12m + 3 = 3(4m + 1) ✓. By induction both statements hold for all n ∈ N.
This lesson ends with a quiz of 18 MCQs. Open the lesson on PrepOasis to take it and save your progress.
Previous: Unit 6 Review, Checklist and Unit Test · Next: 7.2 The Binomial Theorem: Expansion, Pascal's Triangle and the General Term
All lessons in Mathematics XI (HSSC-I) – FBISE Complete SLO-Based Course