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.