Course contentsShow
← Computer Science
Lesson 90 of 2,8722. Discrete Mathematics for CSFree lesson

Summing Series by Induction

Apply induction to prove formulas for arithmetic and geometric series, like 1+2+...+n = n(n+1)/2.

Summing Series by Induction

What you'll learn: How to use mathematical induction to prove formulas for sums like 1+2+3+...+n.

Now that you understand the three-step induction structure (base case, inductive hypothesis, inductive step), let's apply it to prove a classic formula: the sum of the first n positive integers.

The Problem

Suppose you want to add 1 + 2 + 3 + ... + n. There's a famous formula that claims the result is always n(n+1)/2. But how do we prove it works for every positive integer n?

Using Induction

Base Case (n=1): Does the formula work when n=1?

  • Left side: just 1
  • Right side: 1(1+1)/2 = 2/2 = 1 ✓

Inductive Hypothesis: Assume the formula holds for some arbitrary k: 1 + 2 + ... + k = k(k+1)/2

Inductive Step: Prove it works for k+1. We need to show: 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2

Start with the left side. By our hypothesis, we can replace the first k terms:

  • [k(k+1)/2] + (k+1)
  • Factor out (k+1): (k+1)[k/2 + 1]
  • Simplify: (k+1)[(k+2)/2] = (k+1)(k+2)/2 ✓

This matches our target! The domino falls.

Why This Matters

Induction lets you verify formulas that would be impossible to check by testing every number individually. This same technique proves formulas for geometric series (1 + r + r² + ...) and countless others in algorithm analysis.

Key Takeaway: Summing series by induction means proving a sum formula by verifying the base case, assuming it holds for n=k, then algebraically showing it must hold for n=k+1.