Proof by Mathematical Induction (Extension) — Topic Review — Solutions

← Back to Proof by Mathematical Induction (Extension)

This review covers all three lessons in the Proof by Mathematical Induction (Extension) topic: Induction for Series and Sums, Induction for Divisibility and Inequalities, and Induction for Matrices and Complex Numbers. Questions are exam-style and increase in difficulty. Click each question to reveal the full worked solution.

Mixed Review Questions

1. Fluency

   Q1 — Sum of Integers

   Prove by mathematical induction that ∑_k=1ⁿ k = n(n+1)/2 for all positive integers n.

   ▶ Show Answer

   Base case (n = 1):

   LHS = 1.   RHS = 1(1+1)/2 = 1.   LHS = RHS ✓

   Inductive hypothesis: Assume the statement is true for n = k, i.e.,

   1 + 2 + 3 + … + k = k(k+1)/2.

   Inductive step: Prove for n = k + 1, i.e., show 1 + 2 + … + k + (k+1) = (k+1)(k+2)/2.

   LHS = [1 + 2 + … + k] + (k+1)

   = k(k+1)/2 + (k+1)   [by the inductive hypothesis]

   = (k+1)[k/2 + 1]

   = (k+1)(k+2)/2   = RHS ✓

   Conclusion: By the principle of mathematical induction, ∑_k=1ⁿ k = n(n+1)/2 for all n ∈ ℤ⁺.

2. Fluency

   Q2 — Base Case for Divisibility

   Verify the base case for the statement: “3ⁿ − 1 is divisible by 2 for all n ≥ 1.”

   ▶ Show Answer

   Base case (n = 1):

   3¹ − 1 = 3 − 1 = 2

   2 is divisible by 2 (2 = 2 × 1). ✓

   The base case holds. The inductive step would then assume 3^k − 1 = 2m for some integer m, and show 3^k+1 − 1 is also divisible by 2.

   Note: 3^k+1 − 1 = 3 × 3^k − 1 = 3(3^k − 1) + 2 = 3(2m) + 2 = 2(3m + 1), which is divisible by 2.

3. Fluency

   Q3 — Inductive Hypothesis for Sum of Squares

   Write out the inductive hypothesis for proving ∑_k=1ⁿ k² = n(n+1)(2n+1)/6 by mathematical induction.

   ▶ Show Answer

   The inductive hypothesis is the assumption that the statement holds for n = k (some arbitrary positive integer):

   Assume that 1² + 2² + 3² + … + k² = k(k+1)(2k+1)/6.

   We then use this hypothesis in the inductive step to prove the statement holds for n = k + 1, i.e., that:

   1² + 2² + … + k² + (k+1)² = (k+1)(k+2)(2k+3)/6.

4. Fluency

   Q4 — De Moivre’s Theorem Application

   Evaluate (cos(π/4) + i sin(π/4))⁸ using De Moivre’s theorem.

   ▶ Show Answer

   By De Moivre’s theorem: (cosθ + i sinθ)ⁿ = cos(nθ) + i sin(nθ).

   (cos(π/4) + i sin(π/4))⁸ = cos(8 × π/4) + i sin(8 × π/4)

   = cos(2π) + i sin(2π)

   = 1 + 0i

   = 1

5. Fluency

   Q5 — Sum of Odd Integers

   Prove by induction that ∑_k=1ⁿ (2k − 1) = n² for all positive integers n.

   ▶ Show Answer

   Base case (n = 1):

   LHS = 2(1) − 1 = 1.   RHS = 1² = 1.   LHS = RHS ✓

   Inductive hypothesis: Assume 1 + 3 + 5 + … + (2k−1) = k².

   Inductive step: Show the sum to (k+1) terms equals (k+1)².

   LHS = [1 + 3 + … + (2k−1)] + (2(k+1) − 1)

   = k² + (2k + 1)   [by the inductive hypothesis]

   = k² + 2k + 1

   = (k+1)²   = RHS ✓

   Conclusion: By induction, ∑_k=1ⁿ (2k−1) = n² for all n ∈ ℤ⁺.

6. Understanding

   Q6 — Sum of Squares

   Prove by mathematical induction that ∑_k=1ⁿ k² = n(n+1)(2n+1)/6 for all positive integers n.

   ▶ Show Answer

   Base case (n = 1):

   LHS = 1² = 1.   RHS = 1(2)(3)/6 = 6/6 = 1.   LHS = RHS ✓

   Inductive hypothesis: Assume 1² + 2² + … + k² = k(k+1)(2k+1)/6.

   Inductive step: Show 1² + 2² + … + k² + (k+1)² = (k+1)(k+2)(2k+3)/6.

   LHS = k(k+1)(2k+1)/6 + (k+1)²

   = (k+1)[k(2k+1)/6 + (k+1)]

   = (k+1)[k(2k+1) + 6(k+1)] / 6

   = (k+1)(2k² + k + 6k + 6) / 6

   = (k+1)(2k² + 7k + 6) / 6

   = (k+1)(k+2)(2k+3) / 6   = RHS ✓

   Check factoring: (k+2)(2k+3) = 2k² + 3k + 4k + 6 = 2k² + 7k + 6 ✓

   Conclusion: By induction, ∑_k=1ⁿ k² = n(n+1)(2n+1)/6 for all n ∈ ℤ⁺.

7. Understanding

   Q7 — Divisibility by 3

   Prove by induction that 4ⁿ − 1 is divisible by 3 for all n ≥ 1.

   ▶ Show Answer

   Base case (n = 1):

   4¹ − 1 = 3 = 3 × 1.   Divisible by 3. ✓

   Inductive hypothesis: Assume 4^k − 1 = 3m for some integer m (i.e., 3 | 4^k − 1).

   Inductive step: Show 4^k+1 − 1 is divisible by 3.

   4^k+1 − 1 = 4 × 4^k − 1

   = 4 × 4^k − 4 + 3

   = 4(4^k − 1) + 3

   = 4(3m) + 3   [by the inductive hypothesis]

   = 3(4m + 1)

   This is divisible by 3 (since 4m + 1 is an integer). ✓

   Conclusion: By induction, 3 | (4ⁿ − 1) for all n ≥ 1.

8. Understanding

   Q8 — Factorial Inequality

   Prove by induction that n! > 2ⁿ for all n ≥ 4.

   ▶ Show Answer

   Base case (n = 4):

   4! = 24 and 2⁴ = 16.   24 > 16 ✓

   Inductive hypothesis: Assume k! > 2^k for some k ≥ 4.

   Inductive step: Show (k+1)! > 2^k+1.

   (k+1)! = (k+1) × k!

   > (k+1) × 2^k   [by the inductive hypothesis]

   > 2 × 2^k   [since k+1 ≥ 5 > 2 for k ≥ 4]

   = 2^k+1 ✓

   Conclusion: By induction, n! > 2ⁿ for all n ≥ 4.

9. Understanding

   Q9 — Power of a Matrix

   Prove by induction that ⎛1  2⎞ⁿ = ⎛1  2n⎞
   ⎝0  1⎠      ⎝0   1⎠
   for all positive integers n.

   ▶ Show Answer

   Let A = [[1, 2], [0, 1]]. We prove Aⁿ = [[1, 2n], [0, 1]].

   Base case (n = 1):

   A¹ = [[1, 2], [0, 1]] = [[1, 2(1)], [0, 1]] ✓

   Inductive hypothesis: Assume A^k = [[1, 2k], [0, 1]].

   Inductive step: Show A^k+1 = [[1, 2(k+1)], [0, 1]].

   A^k+1 = A^k × A

   = [[1, 2k], [0, 1]] × [[1, 2], [0, 1]]

   = [[1×1 + 2k×0,   1×2 + 2k×1], [0×1 + 1×0,   0×2 + 1×1]]

   = [[1, 2 + 2k], [0, 1]]

   = [[1, 2(k+1)], [0, 1]] ✓

   Conclusion: By induction, Aⁿ = [[1, 2n], [0, 1]] for all n ∈ ℤ⁺.

10. Understanding

    Q10 — De Moivre’s Theorem (Proof)

    Prove De Moivre’s theorem for positive integers: (cosθ + i sinθ)ⁿ = cos(nθ) + i sin(nθ) for all n ∈ ℤ⁺.

    ▶ Show Answer

    Base case (n = 1):

    (cosθ + i sinθ)¹ = cosθ + i sinθ = cos(1·θ) + i sin(1·θ) ✓

    Inductive hypothesis: Assume (cosθ + i sinθ)^k = cos(kθ) + i sin(kθ).

    Inductive step: Show (cosθ + i sinθ)^k+1 = cos((k+1)θ) + i sin((k+1)θ).

    (cosθ + i sinθ)^k+1 = (cosθ + i sinθ)^k × (cosθ + i sinθ)

    = [cos(kθ) + i sin(kθ)] × (cosθ + i sinθ)   [by I.H.]

    = cos(kθ)cosθ − sin(kθ)sinθ + i[sin(kθ)cosθ + cos(kθ)sinθ]

    = cos(kθ + θ) + i sin(kθ + θ)   [compound angle formulas]

    = cos((k+1)θ) + i sin((k+1)θ) ✓

    Conclusion: By induction, De Moivre’s theorem holds for all n ∈ ℤ⁺.

11. Problem Solving

    Q11 — Power vs Square Inequality

    Prove by induction that 2ⁿ > n² for all n ≥ 5.

    ▶ Show Answer

    Base case (n = 5):

    2⁵ = 32 and 5² = 25.   32 > 25 ✓

    Inductive hypothesis: Assume 2^k > k² for some k ≥ 5.

    Inductive step: Show 2^k+1 > (k+1)².

    2^k+1 = 2 × 2^k

    > 2k²   [by the inductive hypothesis]

    We need to show 2k² ≥ (k+1)² = k² + 2k + 1 for k ≥ 5.

    This requires k² − 2k − 1 ≥ 0, i.e., k² ≥ 2k + 1.

    For k ≥ 5: k² = k × k ≥ 5k > 2k + 1 (since 5k > 2k + 1 ⇔ 3k > 1, true for k ≥ 1). ✓

    Therefore 2^k+1 > 2k² ≥ (k+1)². ✓

    Conclusion: By induction, 2ⁿ > n² for all n ≥ 5.

12. Problem Solving

    Q12 — Diagonal Matrix Power

    Prove by induction that ⎛3  0⎞ⁿ = ⎛3ⁿ   0 ⎞
    ⎝0  2⎠      ⎝0   2ⁿ⎠
    for all positive integers n.

    ▶ Show Answer

    Let B = [[3, 0], [0, 2]]. We prove Bⁿ = [[3ⁿ, 0], [0, 2ⁿ]].

    Base case (n = 1):

    B¹ = [[3, 0], [0, 2]] = [[3¹, 0], [0, 2¹]] ✓

    Inductive hypothesis: Assume B^k = [[3^k, 0], [0, 2^k]].

    Inductive step: Show B^k+1 = [[3^k+1, 0], [0, 2^k+1]].

    B^k+1 = B^k × B

    = [[3^k, 0], [0, 2^k]] × [[3, 0], [0, 2]]

    = [[3^k×3 + 0×0,   3^k×0 + 0×2], [0×3 + 2^k×0,   0×0 + 2^k×2]]

    = [[3^k+1, 0], [0, 2^k+1]] ✓

    Conclusion: By induction, Bⁿ = [[3ⁿ, 0], [0, 2ⁿ]] for all n ∈ ℤ⁺.

13. Problem Solving

    Q13 — Triple Angle Formula

    Use De Moivre’s theorem with n = 3 to prove that cos(3θ) = 4cos³θ − 3cosθ.

    ▶ Show Answer

    By De Moivre’s theorem:

    (cosθ + i sinθ)³ = cos(3θ) + i sin(3θ)   … (1)

    Expand the left side using the binomial theorem:

    (cosθ + i sinθ)³

    = cos³θ + 3cos²θ(i sinθ) + 3cosθ(i sinθ)² + (i sinθ)³

    = cos³θ + 3i cos²θ sinθ + 3cosθ(i² sin²θ) + i³ sin³θ

    = cos³θ + 3i cos²θ sinθ − 3cosθ sin²θ − i sin³θ

    = (cos³θ − 3cosθ sin²θ) + i(3cos²θ sinθ − sin³θ)   … (2)

    Equating real parts in (1) and (2):

    cos(3θ) = cos³θ − 3cosθ sin²θ

    = cos³θ − 3cosθ(1 − cos²θ)   [using sin²θ = 1 − cos²θ]

    = cos³θ − 3cosθ + 3cos³θ

    = 4cos³θ − 3cosθ   ✓

14. Problem Solving

    Q14 — Sum Involving Powers of 2

    Prove by induction that ∑_k=1ⁿ k · 2^k = (n − 1) · 2ⁿ⁺¹ + 2 for all positive integers n.

    ▶ Show Answer

    Base case (n = 1):

    LHS = 1 × 2¹ = 2.   RHS = (1−1) × 2² + 2 = 0 + 2 = 2.   LHS = RHS ✓

    Inductive hypothesis: Assume ∑_k=1^m k · 2^k = (m−1) · 2^m+1 + 2.

    Inductive step: Show ∑_k=1^m+1 k · 2^k = m · 2^m+2 + 2.

    ∑_k=1^m+1 k · 2^k = [(m−1) · 2^m+1 + 2] + (m+1) · 2^m+1

    = 2^m+1[(m−1) + (m+1)] + 2

    = 2^m+1 × 2m + 2

    = m × 2^m+2 + 2   = RHS ✓

    Conclusion: By induction, ∑_k=1ⁿ k · 2^k = (n−1) · 2ⁿ⁺¹ + 2 for all n ∈ ℤ⁺.

15. Problem Solving

    Q15 — Telescoping Series

    Prove by induction that 1/(1·2) + 1/(2·3) + … + 1/(n(n+1)) = n/(n+1) for all positive integers n.

    ▶ Show Answer

    Base case (n = 1):

    LHS = 1/(1·2) = 1/2.   RHS = 1/(1+1) = 1/2.   LHS = RHS ✓

    Inductive hypothesis: Assume ∑_k=1^m 1/(k(k+1)) = m/(m+1).

    Inductive step: Show ∑_k=1^m+1 1/(k(k+1)) = (m+1)/(m+2).

    ∑_k=1^m+1 1/(k(k+1)) = m/(m+1) + 1/((m+1)(m+2))

    = [m(m+2) + 1] / [(m+1)(m+2)]

    = (m² + 2m + 1) / [(m+1)(m+2)]

    = (m+1)² / [(m+1)(m+2)]

    = (m+1) / (m+2)   = RHS ✓

    Conclusion: By induction, ∑_k=1ⁿ 1/(k(k+1)) = n/(n+1) for all n ∈ ℤ⁺.