Solutions — Proof by Induction: Summation Formulas

← Back to Questions›Mathematical Induction

1. Q1 — Prove the Triangular Number Formula

   ▶ Show Answer

   Claim: 1 + 2 + … + n = n(n+1)/2 for all n ≥ 1.

   Step 1 — Base case (n = 1): LHS = 1, RHS = 1(2)/2 = 1 ✓

   Step 2 — Inductive hypothesis: Assume 1 + 2 + … + k = k(k+1)/2 for some k ≥ 1.

   Step 3 — Inductive step:

   Sum to k+1 = k(k+1)/2 + (k+1) = (k+1)[k/2 + 1] = (k+1)(k+2)/2 ✓

   Step 4 — Conclusion: By PMI, ∑r = n(n+1)/2 for all n ≥ 1.

2. Q2 — Sum of Odd Numbers

   ▶ Show Answer

   Claim: 1 + 3 + … + (2n − 1) = n² for all n ≥ 1.

   Step 1 — Base case (n = 1): LHS = 1, RHS = 1² = 1 ✓

   Step 2 — Inductive hypothesis: Assume 1 + 3 + … + (2k − 1) = k² for some k ≥ 1.

   Step 3 — Inductive step: The next odd number is 2(k+1) − 1 = 2k + 1.

   Sum to k+1 = k² + (2k + 1) = (k + 1)² ✓

   Step 4 — Conclusion: By PMI, the sum of the first n odd numbers equals n² for all n ≥ 1.

3. Q3 — Sum of Squares

   ▶ Show Answer

   Claim: 1² + 2² + … + n² = n(n+1)(2n+1)/6 for all n ≥ 1.

   Step 1 — Base case (n = 1): LHS = 1, RHS = 1(2)(3)/6 = 1 ✓

   Step 2 — Inductive hypothesis: Assume ∑_r=1^k r² = k(k+1)(2k+1)/6 for some k ≥ 1.

   Step 3 — Inductive step: Target: (k+1)(k+2)(2k+3)/6.

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

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

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

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

   = (k+1)(k+2)(2k+3)/6    [since (k+2)(2k+3) = 2k²+7k+6] ✓

   Step 4 — Conclusion: By PMI, ∑r² = n(n+1)(2n+1)/6 for all n ≥ 1.

4. Q4 — Sum of Cubes

   ▶ Show Answer

   Claim: 1³ + 2³ + … + n³ = [n(n+1)/2]² for all n ≥ 1.

   Step 1 — Base case (n = 1): LHS = 1, RHS = [1(2)/2]² = 1 ✓

   Step 2 — Inductive hypothesis: Assume ∑_r=1^k r³ = [k(k+1)/2]² = k²(k+1)²/4 for some k ≥ 1.

   Step 3 — Inductive step: Target: [(k+1)(k+2)/2]² = (k+1)²(k+2)²/4.

   Sum to k+1 = k²(k+1)²/4 + (k+1)³

   = (k+1)²[k²/4 + (k+1)]

   = (k+1)²(k² + 4k + 4)/4

   = (k+1)²(k+2)²/4 ✓

   Step 4 — Conclusion: By PMI, ∑r³ = [n(n+1)/2]² for all n ≥ 1.

5. Q5 — Telescoping Sum

   ▶ Show Answer

   Claim: ∑_r=1ⁿ 1/(r(r+1)) = n/(n+1) for all n ≥ 1.

   Step 1 — Base case (n = 1): LHS = 1/(1×2) = 1/2, RHS = 1/2 ✓

   Step 2 — Inductive hypothesis: Assume the sum to k equals k/(k+1).

   Step 3 — Inductive step: The (k+1)th term is 1/((k+1)(k+2)).

   Sum to k+1 = k/(k+1) + 1/((k+1)(k+2))

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

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

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

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

   Step 4 — Conclusion: By PMI, ∑1/(r(r+1)) = n/(n+1) for all n ≥ 1.

6. Q6 — Sum of Products of Consecutive Integers

   ▶ Show Answer

   Claim: 1×2 + 2×3 + … + n(n+1) = n(n+1)(n+2)/3 for all n ≥ 1.

   Step 1 — Base case (n = 1): LHS = 2, RHS = 1(2)(3)/3 = 2 ✓

   Step 2 — Inductive hypothesis: Assume the sum to k equals k(k+1)(k+2)/3.

   Step 3 — Inductive step: The (k+1)th term is (k+1)(k+2). Target: (k+1)(k+2)(k+3)/3.

   Sum to k+1 = k(k+1)(k+2)/3 + (k+1)(k+2)

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

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

   Step 4 — Conclusion: By PMI, ∑r(r+1) = n(n+1)(n+2)/3 for all n ≥ 1.

7. Q7 — Geometric Series

   ▶ Show Answer

   Claim: 1 + x + x² + … + xⁿ = (xⁿ⁺¹ − 1)/(x − 1) for all n ≥ 0, x ≠ 1.

   Step 1 — Base case (n = 0): LHS = 1, RHS = (x − 1)/(x − 1) = 1 ✓

   Step 2 — Inductive hypothesis: Assume 1 + x + … + x^k = (x^k+1 − 1)/(x − 1) for some k ≥ 0.

   Step 3 — Inductive step: The next term is x^k+1. Target: (x^k+2 − 1)/(x − 1).

   Sum to k+1 = (x^k+1 − 1)/(x − 1) + x^k+1

   = [(x^k+1 − 1) + x^k+1(x − 1)] / (x − 1)

   = [x^k+2 − 1] / (x − 1) ✓

   Step 4 — Conclusion: By PMI, the geometric series formula holds for all n ≥ 0 when x ≠ 1.

8. Q8 — Sum with Odd Denominators

   ▶ Show Answer

   Claim: ∑_r=1ⁿ 1/((2r−1)(2r+1)) = n/(2n+1) for all n ≥ 1.

   Step 1 — Base case (n = 1): LHS = 1/(1×3) = 1/3, RHS = 1/3 ✓

   Step 2 — Inductive hypothesis: Assume the sum to k equals k/(2k+1).

   Step 3 — Inductive step: The (k+1)th term is 1/((2k+1)(2k+3)). Target: (k+1)/(2k+3).

   Sum to k+1 = k/(2k+1) + 1/((2k+1)(2k+3))

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

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

   = (2k+1)(k+1) / [(2k+1)(2k+3)]    [factorise numerator]

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

   Step 4 — Conclusion: By PMI, the sum equals n/(2n+1) for all n ≥ 1.

9. Q9 — Prove a Product Sum and Apply It

   ▶ Show Answer

   Part (a):

   Step 1: n = 1: LHS = 1×2 = 2, RHS = 1(2)(3)/3 = 2 ✓

   Step 2: Assume 1×2 + … + k(k+1) = k(k+1)(k+2)/3.

   Step 3: Sum to k+1 = k(k+1)(k+2)/3 + (k+1)(k+2) = (k+1)(k+2)[k/3 + 1] = (k+1)(k+2)(k+3)/3 ✓

   Step 4: By PMI, ∑r(r+1) = n(n+1)(n+2)/3 for all n ≥ 1.

   Part (b) — Application (n = 10):

   1×2 + 2×3 + … + 10×11 = 10(11)(12)/3 = 1320/3 = 440

10. Q10 — Sum of Products of Three Consecutive Integers

    ▶ Show Answer

    Claim: ∑_r=1ⁿ r(r+1)(r+2) = n(n+1)(n+2)(n+3)/4 for all n ≥ 1.

    Step 1 — Base case (n = 1): LHS = 1×2×3 = 6, RHS = 1(2)(3)(4)/4 = 6 ✓

    Step 2 — Inductive hypothesis: Assume the sum to k equals k(k+1)(k+2)(k+3)/4.

    Step 3 — Inductive step: The (k+1)th term is (k+1)(k+2)(k+3). Target: (k+1)(k+2)(k+3)(k+4)/4.

    Sum to k+1 = k(k+1)(k+2)(k+3)/4 + (k+1)(k+2)(k+3)

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

    = (k+1)(k+2)(k+3)(k+4)/4 ✓

    Step 4 — Conclusion: By PMI, ∑r(r+1)(r+2) = n(n+1)(n+2)(n+3)/4 for all n ≥ 1.

    Observation: This same pattern generalises — the sum of any such product of m consecutive integers starting at r has formula [n(n+1)…(n+m)] / (m+1).