Practice Maths

Proof by Induction — Summation Formulas

← Back to Mathematical Induction›Specialist Maths

Key Terms

Summation formula
A closed-form expression for a series; e.g. 1 + 2 + … + n = n(n+1)/2.
Key results
∑r = n(n+1)/2; ∑r² = n(n+1)(2n+1)/6; ∑r³ = [n(n+1)/2]².
Inductive hypothesis for sums
Assume the formula holds for n = k: ∑r=1k f(r) = S(k).
Inductive step structure
Write: Sum to k+1 = [Sum to k] + (k+1)th term = S(k) + f(k+1); simplify to show this equals S(k+1).
Factorisation strategy
Factor out (k+1) or other common factors to reach the target formula.
PMI
Abbreviation for the Principle of Mathematical Induction.

Standard Summation Results (Proved by Induction)

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

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

∑r=1n r³ = [n(n+1)/2]²

∑r=1n r(r+1) = n(n+1)(n+2)/3

Geometric sum (x ≠ 1): 1 + x + x² + … + xn = (xn+1 − 1)/(x − 1)

The Four Steps — Applied to Complex Sums

Step 1 — Base case: Substitute n = 1 and confirm LHS = RHS.

Step 2 — Inductive hypothesis: Assume the formula holds for n = k.

Step 3 — Inductive step: Show the formula holds for n = k+1 by writing:

Sum to (k+1) = [Sum to k] + (k+1)th term

= [RHS for n = k, by hypothesis] + (k+1)th term

= … factor and simplify to reach RHS for n = k+1 ✓

Step 4 — Conclusion: State the result holds for all n ≥ 1 by PMI.

Worked Example — Prove ∑r³ = [n(n+1)/2]²

Step 1 (n = 1): LHS = 1³ = 1    RHS = [1(2)/2]² = 1² = 1 ✓

Step 2: Assume 1³ + 2³ + … + k³ = [k(k+1)/2]² for some k ≥ 1.

Step 3: Show the sum to k+1 equals [(k+1)(k+2)/2]².

Sum to k+1 = [k(k+1)/2]² + (k+1)³    [by hypothesis]

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

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

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

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

Hot Tip: In the inductive step for a sum, always write “Sum to k+1 = [Sum to k] + (k+1)th term” as your first line. Then substitute the inductive hypothesis for the sum to k. This structure is predictable and earns method marks even if you make an algebraic slip in the simplification.

Extending the Induction Framework to Harder Sums

The core four-step framework is identical for all summation proofs. What changes is the algebraic complexity of Step 3. This lesson builds fluency with the factoring and simplification techniques needed for the QCAA Specialist Maths syllabus.

The Key Algebraic Technique: Factoring Out (k+1)

In almost every summation induction proof, the critical step is factoring (k+1) from the expression after applying the inductive hypothesis. The general pattern is:

f(k)(k+1)/d + (k+1)m = (k+1)[f(k)/d + (k+1)m−1]

Once (k+1) is factored out, the expression inside the brackets usually simplifies to match the remaining part of the RHS for n = k+1.

Hot Tip — Always Write the Target First:
Before starting Step 3, write out explicitly what the RHS looks like for n = k+1. For example, if the formula is n(n+1)(2n+1)/6, then for n = k+1 it becomes (k+1)(k+2)(2k+3)/6. Knowing your target makes the algebra much more directed.

Telescoping and Partial Fractions Sums

Some sums involve terms like 1/(r(r+1)) or 1/((2r-1)(2r+1)). When proving these by induction, the partial fraction decomposition of the general term is not needed — you only need to add the (k+1)th term to the assumed sum and simplify. The key is to combine fractions correctly over a common denominator.

For example, to prove ∑1/(r(r+1)) = n/(n+1):

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) ✓

Geometric Series

For the geometric series 1 + x + x² + … + xn, the (k+1)th term (i.e. the term added when going from n = k to n = k+1) is xk+1. The proof uses the inductive hypothesis to replace the sum to k, then combines fractions with denominator (x − 1).

Common Mistake: Wrong (k+1)th Term

Always identify the (k+1)th term of the sequence carefully before starting Step 3. If the general term is r(r+1), then the (k+1)th term is (k+1)(k+2), not (k+1)². Getting this wrong invalidates the entire inductive step.

Sum Formula(k+1)th Term to Add
∑r = n(n+1)/2k+1
∑r² = n(n+1)(2n+1)/6(k+1)²
∑r³ = [n(n+1)/2]²(k+1)³
∑r(r+1) = n(n+1)(n+2)/3(k+1)(k+2)
∑1/(r(r+1)) = n/(n+1)1/((k+1)(k+2))

Mastery Practice

  1. Fluency

    Q1 — Prove the Triangular Number Formula

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

  2. Fluency

    Q2 — Sum of Odd Numbers

    Prove by mathematical induction that 1 + 3 + 5 + … + (2n − 1) = n² for all integers n ≥ 1.

  3. Fluency

    Q3 — Sum of Squares

    Prove by mathematical induction that 1² + 2² + 3² + … + n² = n(n+1)(2n+1)/6 for all integers n ≥ 1.

  4. Fluency

    Q4 — Sum of Cubes

    Prove by mathematical induction that 1³ + 2³ + 3³ + … + n³ = [n(n+1)/2]² for all integers n ≥ 1.

  5. Understanding

    Q5 — Telescoping Sum

    Prove by mathematical induction that

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

  6. Understanding

    Q6 — Sum of Products of Consecutive Integers

    Prove by mathematical induction that

    1×2 + 2×3 + 3×4 + … + n(n+1) = n(n+1)(n+2)/3   for all integers n ≥ 1.

  7. Understanding

    Q7 — Geometric Series

    Prove by mathematical induction that for x ≠ 1:

    1 + x + x² + … + xn = (xn+1 − 1)/(x − 1)   for all integers n ≥ 0.

    Note: the base case here is n = 0 (a single term).

  8. Understanding

    Q8 — Sum with Odd Denominators

    Prove by mathematical induction that

    ∑r=1n 1/((2r−1)(2r+1)) = n/(2n+1)   for all integers n ≥ 1.

  9. Problem Solving

    Q9 — Prove a Product Sum and Apply It

    (a) Prove by mathematical induction that 1×2 + 2×3 + … + n(n+1) = n(n+1)(n+2)/3 for all n ≥ 1.

    (b) Hence, find the exact value of 1×2 + 2×3 + … + 10×11.

  10. Problem Solving

    Q10 — Sum of Products of Three Consecutive Integers

    Prove by mathematical induction that

    1×2×3 + 2×3×4 + … + n(n+1)(n+2) = n(n+1)(n+2)(n+3)/4   for all integers n ≥ 1.

See Answers ➔