Practice Maths

← Proof by Mathematical Induction › Induction for Series and Sums › Solutions

Induction for Series and Sums — Full Worked Solutions

  1. Verify the base case and write out the inductive hypothesis for each statement. Fluency

    (a) P(n): ∑r=1n r = n(n+1)/2

    Base case n=1: LHS = 1. RHS = 1(2)/2 = 1. LHS = RHS. ✓

    Inductive hypothesis: Assume ∑r=1k r = k(k+1)/2 for some integer k ≥ 1.

    (b) P(n): ∑r=1n (2r−1) = n²

    Base case n=1: LHS = 2(1)−1 = 1. RHS = 1² = 1. ✓

    Inductive hypothesis: Assume ∑r=1k (2r−1) = k² for some integer k ≥ 1.

    (c) P(n): ∑r=1n r(r+1) = n(n+1)(n+2)/3

    Base case n=1: LHS = 1(2) = 2. RHS = 1(2)(3)/3 = 2. ✓

    Inductive hypothesis: Assume ∑r=1k r(r+1) = k(k+1)(k+2)/3 for some integer k ≥ 1.

  2. Complete the inductive step. Fluency

    We need to show ∑r=1k+1 (2r−1) = (k+1)².

    LHS = ∑r=1k (2r−1) + (2(k+1)−1)

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

    = k² + 2k + 1

    = (k+1)² = RHS. ✓

    Since P(1) is true and P(k) ⇒ P(k+1), by mathematical induction P(n) is true for all n ≥ 1.

  3. Prove ∑r=1n r(r+1) = n(n+1)(n+2)/3. Fluency

    Claim: P(n): ∑r=1n r(r+1) = n(n+1)(n+2)/3 for all integers n ≥ 1.

    Base case n=1: LHS = 1(2) = 2. RHS = 1(2)(3)/3 = 2. LHS = RHS. ✓

    Inductive hypothesis: Assume ∑r=1k r(r+1) = k(k+1)(k+2)/3 for some integer k ≥ 1.

    Inductive step: We must show ∑r=1k+1 r(r+1) = (k+1)(k+2)(k+3)/3.

    LHS = ∑r=1k r(r+1) + (k+1)(k+2)

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

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

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

    Conclusion: By the principle of mathematical induction, P(n) is true for all integers n ≥ 1.

  4. Prove 1 + 3 + 5 + … + (2n−1) = n². Fluency

    Claim: P(n): ∑r=1n (2r−1) = n² for all integers n ≥ 1.

    Base case n=1: LHS = 2(1)−1 = 1. RHS = 1² = 1. ✓

    Inductive hypothesis: Assume ∑r=1k (2r−1) = k².

    Inductive step: Show ∑r=1k+1 (2r−1) = (k+1)².

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

    Conclusion: By mathematical induction, true for all n ≥ 1.

  5. Prove ∑r=1n r² = n(n+1)(2n+1)/6. Understanding

    Claim: P(n): ∑r=1n r² = n(n+1)(2n+1)/6 for all integers n ≥ 1.

    Base case n=1: LHS = 1² = 1. RHS = 1(2)(3)/6 = 1. LHS = RHS. ✓

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

    Inductive step: We must show ∑r=1k+1 r² = (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. ✓     [factorising 2k²+7k+6 = (k+2)(2k+3)]

    Conclusion: By the principle of mathematical induction, P(n) is true for all integers n ≥ 1.

  6. Prove ∑r=1n r³ = [n(n+1)/2]². Understanding

    Claim: P(n): ∑r=1n r³ = n²(n+1)²/4 for all integers n ≥ 1.

    Base case n=1: LHS = 1³ = 1. RHS = 1(4)/4 = 1. ✓

    Inductive hypothesis: Assume ∑r=1k r³ = k²(k+1)²/4.

    Inductive step: Show ∑r=1k+1 r³ = (k+1)²(k+2)²/4.

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

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

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

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

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

    Conclusion: By mathematical induction, true for all n ≥ 1.

  7. Prove ∑r=0n−1 2r = 2n − 1. Understanding

    Claim: P(n): ∑r=0n−1 2r = 2n − 1 for all integers n ≥ 1.

    Base case n=1: LHS = 2⁰ = 1. RHS = 2¹ − 1 = 1. ✓

    Inductive hypothesis: Assume ∑r=0k−1 2r = 2k − 1 for some k ≥ 1.

    Inductive step: Show ∑r=0k 2r = 2k+1 − 1.

    LHS = ∑r=0k−1 2r + 2k

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

    = 2 × 2k − 1 = 2k+1 − 1 = RHS. ✓

    Conclusion: By mathematical induction, true for all n ≥ 1.

  8. Prove ∑r=1n 1/(r(r+1)) = n/(n+1). Understanding

    Claim: P(n): ∑r=1n 1/(r(r+1)) = n/(n+1) for all integers n ≥ 1.

    Base case n=1: LHS = 1/(1×2) = 1/2. RHS = 1/2. ✓

    Inductive hypothesis: Assume ∑r=1k 1/(r(r+1)) = k/(k+1).

    Inductive step: Show ∑r=1k+1 1/(r(r+1)) = (k+1)/(k+2).

    LHS = k/(k+1) + 1/((k+1)(k+2))     [by IH]

    = [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) = RHS. ✓

    Conclusion: By mathematical induction, true for all n ≥ 1.

  9. Find and verify a closed form for ∑ r(r+2). Problem Solving

    Finding the closed form:

    ∑r=1n r(r+2) = ∑r=1n (r² + 2r) = ∑r² + 2∑r

    = n(n+1)(2n+1)/6 + 2 × n(n+1)/2

    = n(n+1)(2n+1)/6 + n(n+1)

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

    = n(n+1)(2n+7)/6

    Proof by induction:

    Claim: ∑r=1n r(r+2) = n(n+1)(2n+7)/6.

    Base case n=1: LHS = 1(3) = 3. RHS = 1(2)(9)/6 = 3. ✓

    Inductive hypothesis: Assume ∑r=1k r(r+2) = k(k+1)(2k+7)/6.

    Inductive step: Show the result for k+1.

    LHS = k(k+1)(2k+7)/6 + (k+1)(k+3)

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

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

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

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

    = (k+1)(k+2)(2k+9)/6     [since 2k²+13k+18 = (k+2)(2k+9)]

    = (k+1)(k+2)(2(k+1)+7)/6 = RHS. ✓

    Conclusion: By mathematical induction, true for all n ≥ 1.

  10. Prove or disprove: ∑ r³ = [∑ r]². Problem Solving

    This statement is TRUE.

    We have: ∑r=1n r³ = [n(n+1)/2]² and ∑r=1n r = n(n+1)/2.

    Therefore [∑r=1n r]² = [n(n+1)/2]² = ∑r=1n r³. The identity holds for all n ≥ 1.

    Proof by induction:

    Claim: P(n): ∑r=1n r³ = [∑r=1n r]² for all n ≥ 1.

    This is equivalent to showing ∑r³ = [n(n+1)/2]², already proved in Q6. Since both sides equal n²(n+1)²/4, the identity is established. By mathematical induction (the proof in Q6), it holds for all n ≥ 1.