Proving Summation Formulas by Induction
Simple Explanation
Many formulas that add up a pattern of numbers (like 1+2+...+n) can be proved correct for every n using induction — the inductive step typically involves adding the NEW term (the (k+1)th term) to both sides of the assumed formula at n=k.
Why Do We Need It?
Summation formulas let you add up huge numbers of terms instantly instead of one at a time, and induction is how these formulas are actually verified as correct, not just guessed.
Formula
Sum of the First n Positive Integers
1 + 2 + 3 + ... + n = n(n+1) / 2
The sum of every positive integer from 1 up to n, provable by mathematical induction.
- n
- — the largest integer included in the sum, a positive integer
When to use it: Whenever the sum of consecutive integers from 1 to n is needed directly, without adding them one by one.
Worked Example
Prove the formula for the sum of the first n positive integers
Prove that 1+2+3+...+n = n(n+1)/2 for all positive integers n ≥ 1.
Why Does This Work?
The inductive hypothesis gives the sum of the first k terms; adding exactly the next term, (k+1), to both sides of that equation is what correctly extends the claim to n=k+1 — the right side then just needs ordinary algebra (factoring) to be reshaped into the form the formula predicts for n=k+1.
Real-Life Example
Computing the total number of unique connections in a growing network
A network engineer needs a formula for the total number of unique cable connections needed to directly connect every pair among n junction boxes.
A summation formula (related to 1+2+...+(n-1)) gives this instantly for any n — and induction is exactly how such a formula gets rigorously verified as correct for every possible n.
Practice
Using 1+2+...+n = n(n+1)/2, find the sum of the first 10 positive integers.
MediumCommon mistake
In the inductive step, forgetting to explicitly add the NEW term (k+1) to both sides — simply substituting n=k+1 into the formula without connecting it back to the inductive hypothesis is not a valid proof.
Quick Review
- Add the (k+1)th term to both sides of the inductive hypothesis.
- Then use algebra (usually factoring) to match the formula's predicted form at n=k+1.
- 1+2+...+n = n(n+1)/2 is a classic example, provable this way.