Practice Maths

Induction for Series and Sums

Key Terms

Proof by mathematical induction
establishes that a statement P(n) is true for all positive integers n ≥ n₀ by two steps.
Step 1 — Base case
Verify P(n₀) is true directly (usually n = 1).
Step 2 — Inductive step
Assume P(k) is true (the inductive hypothesis), then prove P(k+1) is true.
The conclusion follows: since P(1) is true and P(k) ⇒ P(k+1), we conclude P(n) is true for all n ≥ 1.
For summation proofs, the strategy is: write out P(k+1), substitute the sum for k terms using P(k), then algebraically simplify to match the formula with n = k+1.
Key Summation Formulas (provable 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 arr−1 = a(rn−1)/(r−1), r ≠ 1 (geometric series)
Hot Tip The key move in every induction proof for sums: P(k+1) says the sum to k+1 terms equals [sum to k terms] + (k+1)th term. Substitute the inductive hypothesis for the sum to k terms, then factorise to get the formula with n = k+1.

Worked Example 1 — Prove ∑r=1n r = n(n+1)/2

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

Inductive hypothesis: Assume true for n = k: ∑r=1k r = k(k+1)/2.

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

LHS = ∑r=1k r + (k+1) = k(k+1)/2 + (k+1) [by inductive hypothesis]

= (k+1)[k/2 + 1] = (k+1)(k+2)/2 = RHS. ✓

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

Worked Example 2 — Prove ∑r=1n r² = n(n+1)(2n+1)/6

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

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

Inductive step: 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² + 7k + 6)/6 = (k+1)(k+2)(2k+3)/6 = RHS. ✓

Conclusion: True for all integers n ≥ 1 by mathematical induction.

The Logic Behind Mathematical Induction

Mathematical induction is often compared to an infinite row of dominoes. If you can knock the first one over (base case) and guarantee that whenever any domino falls the next one also falls (inductive step), then every domino in the row will eventually fall. This is not a metaphor — it is exactly the logical structure of the proof.

Formally, the principle of mathematical induction states: if P(1) is true, and for every k ≥ 1 the truth of P(k) implies the truth of P(k+1), then P(n) is true for all n ≥ 1. This is an axiom of the natural numbers (specifically the well-ordering principle). You do not need to prove it — you use it.

The power of induction is that it converts an infinite statement ("true for all n") into two finite statements (true for one base case, and a logical implication). Both are verifiable in finite steps.

Structure of a Correct Induction Proof

Every induction proof must contain exactly these four components, clearly labelled:

  1. Claim: State precisely what you are proving, e.g. "Let P(n) be the statement ∑r=1n r = n(n+1)/2."
  2. Base case: Verify P(1) explicitly. Show LHS = RHS by direct calculation. Do not skip this — even if it seems obvious.
  3. Inductive hypothesis: Write "Assume P(k) is true for some integer k ≥ 1," then write out exactly what this assumes.
  4. Inductive step: Starting from the LHS of P(k+1), use the inductive hypothesis, then simplify algebraically until you reach the RHS of P(k+1). Conclude that P(k) ⇒ P(k+1).

The conclusion paragraph is also mandatory: "By the principle of mathematical induction, P(n) is true for all integers n ≥ 1." This sentence makes the logical chain explicit and shows the proof is complete.

Strategy for Sum Formulas: The Key Substitution

For a statement of the form P(n): "∑r=1n f(r) = F(n)", the inductive step always begins the same way. You want to prove P(k+1), which says:

∑r=1k+1 f(r) = F(k+1)

The crucial observation: ∑r=1k+1 f(r) = [∑r=1k f(r)] + f(k+1). The first bracket is exactly what P(k) says equals F(k). So substitute:

= F(k) + f(k+1)

Now your job is purely algebraic: simplify F(k) + f(k+1) until it equals F(k+1). This typically involves factorising. Extract the common factor carefully — this is where most errors occur.

Proving the Sum of Cubes: ∑ r³ = [n(n+1)/2]²

This is among the most elegant sum formulas. Note that [n(n+1)/2]² is the square of the triangular number formula. The inductive step requires showing:

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

Factor out (k+1)²: (k+1)²[k²/4 + (k+1)] = (k+1)²[k² + 4k + 4]/4 = (k+1)²(k+2)²/4 = [(k+1)(k+2)/2]². ✓

This shows the sum of the first n cubes is always a perfect square — a beautiful result.

Geometric Series by Induction

The geometric series formula ∑r=1n arr−1 = a(rn−1)/(r−1) (r ≠ 1) can also be proved by induction. The inductive step adds the (k+1)th term ark to the sum a(rk−1)/(r−1), then combines over a common denominator to get a(rk+1−1)/(r−1).

Common Errors and How to Avoid Them

  • Assuming what you want to prove: The inductive hypothesis assumes P(k). The inductive step must prove P(k+1) from scratch using P(k) — you cannot assume P(k+1) anywhere in your working.
  • Poor algebraic manipulation: Factorising incorrectly is the most common error. Always extract the full common factor and double-check your factorisation by expanding back.
  • Missing the conclusion: Without the formal conclusion sentence, the proof is logically incomplete. Always end with "by the principle of mathematical induction..."
  • Checking only one case: Verifying the formula for n = 1, 2, 3 is not a proof — it is evidence. Only induction constitutes a proof for all n.
Exam Tip: In the inductive step, always start from the LHS of P(k+1) and work towards the RHS. Never start from both sides and meet in the middle — this is a logical error in a proof (though fine for scratch work). Your proof must flow in one direction.
Exam Tip: When factorising in the inductive step, the factor (k+1) almost always appears. Extract it first from all terms, then deal with what remains inside the bracket. If the formula for P(k+1) starts with (k+1)(k+2)/..., you know to look for a factor of (k+1) in your algebraic manipulation.

Mastery Practice

See Answers ➔

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

    1. (a) P(n): ∑r=1n r = n(n+1)/2
    2. (b) P(n): ∑r=1n (2r−1) = n²
    3. (c) P(n): ∑r=1n r(r+1) = n(n+1)(n+2)/3

  2. Complete the inductive step. Fluency

    Assume ∑r=1k (2r−1) = k². Show that ∑r=1k+1 (2r−1) = (k+1)². Write out all steps including the substitution and factorisation.

  3. Prove by mathematical induction. Fluency

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

  4. Prove by mathematical induction. Fluency

    Prove that for all integers n ≥ 1: 1 + 3 + 5 + … + (2n−1) = n². (The sum of the first n odd numbers equals n².)

  5. Prove by mathematical induction. Understanding

    Prove that for all integers n ≥ 1: ∑r=1n r² = n(n+1)(2n+1)/6. You must clearly label all four components: claim, base case, inductive hypothesis, inductive step, and conclusion.

  6. Prove by mathematical induction. Understanding

    Prove that for all integers n ≥ 1: ∑r=1n r³ = [n(n+1)/2]².

  7. Geometric series by induction. Understanding

    Prove by induction that for all integers n ≥ 1: ∑r=0n−1 2r = 2n − 1. (The sum of the first n terms of a geometric series with first term 1 and common ratio 2.)

  8. Partial sums by induction. Understanding

    Prove by mathematical induction that for all integers n ≥ 1:

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

    (Hint: first observe that 1/(r(r+1)) = 1/r − 1/(r+1), a telescoping decomposition, but prove the result by induction without using this shortcut.)

  9. Combined sum formula. Problem Solving

    Using the results for ∑r and ∑r² (which you may quote), find a closed form for ∑r=1n r(r+2). Then verify your formula by induction.

  10. Prove or disprove. Problem Solving

    Challenge. A student claims that ∑r=1n r³ = [∑r=1n r]². Is this true? If so, prove it by induction. If not, provide a counterexample.