Mathematical Induction — Topic Review — Solutions
← Back to Mathematical Induction
This review covers all four lessons in the Mathematical Induction topic: Introduction to Induction, Summation Formulas, Divisibility, and Inequalities. All questions use click-to-reveal answers.
Question 1 Fluency — Introduction to Induction
State the four steps of proof by mathematical induction.
Step 1 — Base case: Verify that P(1) (or P(n0 )) is true for the first value of n.
Step 2 — Inductive hypothesis: Assume P(k) is true for some integer k ≥ 1 (or k ≥ n0 ).
Step 3 — Inductive step: Using the assumption that P(k) is true, prove that P(k+1) is also true.
Step 4 — Conclusion: By the principle of mathematical induction, P(n) is true for all integers n ≥ 1 (or n ≥ n0 ).
Question 2 Fluency — Summation
Prove by mathematical induction that ∑k=1 n k = n(n+1)/2 for all integers n ≥ 1.
Base (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 + 1] = (k+1)(k+2)/2 = (k+1)((k+1)+1)/2. ✓
Conclusion: By PMI, ∑k=1 n k = n(n+1)/2 for all integers n ≥ 1.
Question 3 Fluency — Summation
Prove by mathematical induction that ∑k=1 n k2 = n(n+1)(2n+1)/6 for all integers n ≥ 1.
Base (n = 1): LHS = 1. RHS = 1(2)(3)/6 = 1. ✓
Hypothesis: Assume ∑ k2 to k = k(k+1)(2k+1)/6.
Step:
∑ to (k+1) = k(k+1)(2k+1)/6 + (k+1)2
= (k+1)[k(2k+1)/6 + (k+1)]
= (k+1) × [k(2k+1) + 6(k+1)] / 6
= (k+1)(2k2 + k + 6k + 6) / 6
= (k+1)(2k2 + 7k + 6) / 6
= (k+1)(k+2)(2k+3) / 6 [factorising 2k2 +7k+6 = (k+2)(2k+3)]
= (k+1)((k+1)+1)(2(k+1)+1) / 6. ✓
Conclusion: By PMI, ∑k=1 n k2 = n(n+1)(2n+1)/6 for all integers n ≥ 1.
Question 4 Understanding — Summation
Prove by mathematical induction that ∑k=1 n (2k−1) = n2 for all integers n ≥ 1.
Base (n = 1): LHS = 2(1)−1 = 1. RHS = 12 = 1. ✓
Hypothesis: Assume 1 + 3 + 5 + … + (2k−1) = k2 .
Step:
1 + 3 + … + (2k−1) + (2(k+1)−1) = k2 + (2k+1) = k2 + 2k + 1 = (k+1)2 . ✓
Conclusion: By PMI, ∑k=1 n (2k−1) = n2 for all integers n ≥ 1.
Question 5 Fluency — Divisibility
Prove by mathematical induction that 4n − 1 is divisible by 3 for all integers n ≥ 1.
Base (n = 1): 41 − 1 = 3 = 3(1). ✓
Hypothesis: Assume 4k − 1 = 3m for some integer m, so 4k = 3m+1.
Step:
4k+1 − 1 = 4 · 4k − 1 = 4(3m+1) − 1 = 12m + 3 = 3(4m+1).
Since 4m+1 is an integer, 4k+1 − 1 is divisible by 3. ✓
Conclusion: By PMI, 4n − 1 is divisible by 3 for all integers n ≥ 1.
Question 6 Understanding — Divisibility
Prove by mathematical induction that 9n − 1 is divisible by 8 for all integers n ≥ 1.
Base (n = 1): 91 − 1 = 8 = 8(1). ✓
Hypothesis: Assume 9k − 1 = 8m for some integer m, so 9k = 8m+1.
Step:
9k+1 − 1 = 9 · 9k − 1 = 9(8m+1) − 1 = 72m + 9 − 1 = 72m + 8 = 8(9m+1).
Since 9m+1 is an integer, 9k+1 − 1 is divisible by 8. ✓
Conclusion: By PMI, 9n − 1 is divisible by 8 for all integers n ≥ 1.
Question 7 Understanding — Divisibility
Prove by mathematical induction that 5n + 3 is divisible by 4 for all integers n ≥ 1.
Base (n = 1): 51 + 3 = 8 = 4(2). ✓
Hypothesis: Assume 5k + 3 = 4m for some integer m, so 5k = 4m−3.
Step:
5k+1 + 3 = 5 · 5k + 3 = 5(4m−3) + 3 = 20m − 15 + 3 = 20m − 12 = 4(5m−3).
Since 5m−3 is an integer, 5k+1 + 3 is divisible by 4. ✓
Conclusion: By PMI, 5n + 3 is divisible by 4 for all integers n ≥ 1.
Question 8 Problem Solving — Divisibility
Prove by mathematical induction that n3 + 2n is divisible by 3 for all integers n ≥ 1.
Base (n = 1): 13 + 2(1) = 3 = 3(1). ✓
Hypothesis: Assume k3 + 2k = 3m for some integer m.
Step:
(k+1)3 + 2(k+1) = k3 + 3k2 + 3k + 1 + 2k + 2
= (k3 + 2k) + 3k2 + 3k + 3
= 3m + 3(k2 + k + 1)
= 3(m + k2 + k + 1).
Since m + k2 + k + 1 is an integer, the result is divisible by 3. ✓
Conclusion: By PMI, n3 + 2n is divisible by 3 for all integers n ≥ 1.
Question 9 Fluency — Inequalities
Prove by mathematical induction that 2n > n for all integers n ≥ 1.
Base (n = 1): 21 = 2 > 1. ✓
Hypothesis: Assume 2k > k for some integer k ≥ 1.
Step:
2k+1 = 2 × 2k > 2k [by hypothesis]
And 2k = k + k ≥ k + 1 for k ≥ 1 (since k ≥ 1). ✓
Therefore 2k+1 > 2k ≥ k+1, so 2k+1 > k+1. ✓
Conclusion: By PMI, 2n > n for all integers n ≥ 1.
Question 10 Understanding — Inequalities
Prove by mathematical induction that n! ≥ 2n−1 for all integers n ≥ 1.
Base (n = 1): 1! = 1 = 20 = 1. ✓
Hypothesis: Assume k! ≥ 2k−1 for some integer k ≥ 1.
Step:
(k+1)! = (k+1) × k! ≥ (k+1) × 2k−1 [by hypothesis]
Since k ≥ 1, k+1 ≥ 2, so (k+1) × 2k−1 ≥ 2 × 2k−1 = 2k .
Therefore (k+1)! ≥ 2k = 2(k+1)−1 . ✓
Conclusion: By PMI, n! ≥ 2n−1 for all integers n ≥ 1.
Question 11 Understanding — Inequalities
Prove by mathematical induction that 3n ≥ 2n+1 for all integers n ≥ 1.
Base (n = 1): 31 = 3 ≥ 3 = 2(1)+1. ✓
Hypothesis: Assume 3k ≥ 2k+1 for some integer k ≥ 1.
Step:
3k+1 = 3 × 3k ≥ 3(2k+1) = 6k+3 [by hypothesis]
Since 4k ≥ 0 for k ≥ 1: 6k+3 ≥ 2k+3 = 2(k+1)+1. ✓
Therefore 3k+1 ≥ 6k+3 ≥ 2(k+1)+1. ✓
Conclusion: By PMI, 3n ≥ 2n+1 for all integers n ≥ 1.
Question 12 Problem Solving — Summation
Prove by mathematical induction that ∑k=1 n 1/(k(k+1)) = n/(n+1) for all integers n ≥ 1.
Base (n = 1): 1/(1 × 2) = 1/2 = 1/(1+1). ✓
Hypothesis: Assume ∑k=1 k 1/(k(k+1)) = k/(k+1).
Step:
k/(k+1) + 1/((k+1)(k+2)) = [k(k+2) + 1] / [(k+1)(k+2)]
= (k2 + 2k + 1) / [(k+1)(k+2)]
= (k+1)2 / [(k+1)(k+2)]
= (k+1) / (k+2). ✓
Conclusion: By PMI, ∑k=1 n 1/(k(k+1)) = n/(n+1) for all integers n ≥ 1.
Question 13 Understanding — Divisibility
Prove by mathematical induction that 23n − 1 is divisible by 7 for all integers n ≥ 1.
Observation: 23n = (23 )n = 8n , so we prove 8n − 1 is divisible by 7.
Base (n = 1): 81 − 1 = 7 = 7(1). ✓
Hypothesis: Assume 8k − 1 = 7m for some integer m, so 8k = 7m+1.
Step:
8k+1 − 1 = 8 · 8k − 1 = 8(7m+1) − 1 = 56m + 8 − 1 = 56m + 7 = 7(8m+1).
Since 8m+1 is an integer, 8k+1 − 1 is divisible by 7. ✓
Conclusion: By PMI, 23n − 1 is divisible by 7 for all integers n ≥ 1.
Question 14 Problem Solving — Inequalities
Prove by mathematical induction that 2n ≥ n2 for all integers n ≥ 4.
Base (n = 4): 24 = 16 = 42 . ✓ (equality holds)
Hypothesis: Assume 2k ≥ k2 for some integer k ≥ 4.
Step:
2k+1 = 2 × 2k ≥ 2k2 [by hypothesis]
Need 2k2 ≥ (k+1)2 = k2 +2k+1, i.e. k2 −2k−1 ≥ 0.
For k ≥ 4: k2 −2k−1 ≥ 16−8−1 = 7 > 0. ✓
Therefore 2k+1 ≥ 2k2 ≥ (k+1)2 . ✓
Conclusion: By PMI, 2n ≥ n2 for all integers n ≥ 4.
Question 15 Problem Solving — Summation
Prove by mathematical induction that ∑k=1 n k · k! = (n+1)! − 1 for all integers n ≥ 1.
Base (n = 1): 1 × 1! = 1. (1+1)! − 1 = 2! − 1 = 1. ✓
Hypothesis: Assume 1·1! + 2·2! + … + k·k! = (k+1)! − 1.
Step:
[1·1! + 2·2! + … + k·k!] + (k+1)(k+1)!
= (k+1)! − 1 + (k+1)(k+1)! [by hypothesis]
= (k+1)![1 + (k+1)] − 1
= (k+1)!(k+2) − 1
= (k+2)! − 1 [since (k+2)! = (k+2)(k+1)!]
= ((k+1)+1)! − 1. ✓
Conclusion: By PMI, ∑k=1 n k · k! = (n+1)! − 1 for all integers n ≥ 1.
← Review Questions
⌂ Back to Topic