1
Peel off the last term
Σ_{i≤k+1} f(i) = (Σ_{i≤k} f(i)) + f(k+1). This split is what lets the hypothesis apply to the first part.
Lesson · Induction and Recursion · Induction
Induction with Sums and Products
Sums of integers, squares, cubes, geometric series and telescoping sums, and one product to show the pattern does not care which operation it is peeling. Every proof has the same shape, and recognising it makes these routine.
Σ i = n(n+1)/2
Σ i² = n(n+1)(2n+1)/6
Σ i³ = (n(n+1)/2)² = (Σ i)²
Σ arⁱ = a(rⁿ⁺¹ − 1)/(r − 1) geometric, r ≠ 1
Four identities worth knowing
Core ideas
What this lesson establishes
These proofs are mechanical once the pattern is visible: peel, substitute, factor.
2
Substitute the hypothesis
Replace the sum to k by its closed form. From here it is algebra with no sums in it.
3
Factor toward the target
Write the claim at k+1 first, so you know what you are aiming at. Working without a target is how these proofs stall.
The material
The standard sums
Notation, then the proofs, then a route that avoids induction entirely.
Definition · Summation notation
Σ_{i=1}^{n} f(i) means f(1) + f(2) + ⋯ + f(n). The index i is bound; the sum is empty and equal to 0 when the upper limit is below the lower. Products use Π and an empty product is 1.
Theorem · Sum of squares
For n ≥ 1, 1² + 2² + ⋯ + n² = n(n+1)(2n+1)/6.
Base. At n = 1: left is 1, right is 1 · 2 · 3 / 6 = 1.
Step. Assume the identity at k. Then
Σ_{i≤k+1} i² = k(k+1)(2k+1)/6 + (k+1)² by the hypothesis = (k+1)[k(2k+1) + 6(k+1)]/6 = (k+1)(2k² + 7k + 6)/6 = (k+1)(k+2)(2k+3)/6,
which is the claim at k+1, since 2(k+1)+1 = 2k+3.
□
The factoring step 2k² + 7k + 6 = (k+2)(2k+3) is the only place cleverness is required, and it is found by knowing the target: the claim at k+1 must contain (k+2), so (k+2) is what to look for.
Theorem · Geometric series
For r ≠ 1 and n ≥ 0, a + ar + ar² + ⋯ + arⁿ = a(rⁿ⁺¹ − 1)/(r − 1).
Base. At n = 0 the left is a and the right is a(r − 1)/(r − 1) = a.
Step. Assume the formula at k. Adding the next term,
a(r^{k+1} − 1)/(r − 1) + ar^{k+1} = [a(r^{k+1} − 1) + ar^{k+1}(r − 1)]/(r − 1) = a(r^{k+2} − 1)/(r − 1),
which is the claim at k+1.
□
The condition r ≠ 1 is not decoration: at r = 1 the denominator vanishes and the sum is simply a(n+1). Every hypothesis in a theorem statement is doing work somewhere, and finding where is a good habit.
Telescoping, and proofs without induction
Some sums collapse without any induction at all. If f(i) = g(i) − g(i−1), then Σ_{i=1}^{n} f(i) = g(n) − g(0), because every intermediate term appears once positively and once negatively.
Example · A telescoping sum
Σ_{i=1}^{n} 1/(i(i+1)). Since 1/(i(i+1)) = 1/i − 1/(i+1), the sum is (1 − 1/2) + (1/2 − 1/3) + ⋯ + (1/n − 1/(n+1)) = 1 − 1/(n+1) = n/(n+1). No induction needed, though induction would work.
Gauss's pairing argument for Σ i is another such route: add the sum to its own reversal, obtaining n copies of n+1, hence n(n+1)/2. Induction verifies a formula you already have; arguments like these produce one.
Products
Π behaves exactly as Σ does under induction: the product to k+1 is the product to k times one more factor, so the step peels the last factor off instead of the last term, substitutes the hypothesis, and factors toward the target. Nothing else changes.
Theorem · A telescoping product
For n ≥ 2, Π_{i=2}^{n} (1 − 1/i²) = (n+1)/(2n).
Base. At n = 2: left is 1 − 1/4 = 3/4, right is 3/(2 · 2) = 3/4.
Step. Assume the identity at k ≥ 2. Peel off the last factor: Π_{i≤k+1} (1 − 1/i²) = [(k+1)/(2k)] · (1 − 1/(k+1)²) by the hypothesis.
The target is (k+2)/(2(k+1)), so (k+2) is what to look for: 1 − 1/(k+1)² = ((k+1)² − 1)/(k+1)² = k(k+2)/(k+1)². Then [(k+1)/(2k)] · [k(k+2)/(k+1)²] = (k+2)/(2(k+1)), the claim at k+1.
□
The factoring (k+1)² − 1 = k(k+2) is a difference of two squares, found by knowing the target contained (k+2). Written out, the product is (1·3/2²)(2·4/3²)(3·5/4²)⋯, and the same cancellation that collapsed the telescoping sum collapses it to (n+1)/(2n) — which is a check on the answer, not the proof of it.
Interactive
Check P(n), then notice checking is not proving
Two of these statements are false
Method
Proving a sum identity
Write the target first; the algebra then has somewhere to go.
1
Write the claim at k+1 before starting
Substituting k+1 into the formula tells you what the algebra must produce. Working forward blindly is how these stall.
2
Peel the last term off the sum
Σ_{i≤k+1} = (Σ_{i≤k}) + f(k+1), and for a product the last factor: Π_{i≤k+1} = (Π_{i≤k}) · f(k+1). This is the only structural move.
3
Substitute the hypothesis and factor
Take out the common factor — usually (k+1) — and simplify what remains toward the target.
4
Check the base case at the right place
n = 0 and n = 1 are different starting points and give different base cases. Use whichever the statement claims.
Sums
Score 0 / 0Choose the answer you can justify.
Prove Σ_{i=1}^{n} i·i! = (n+1)! − 1
A less familiar identity, same shape of proof.
BASE n = 1: left = 1·1! = 1, right = 2! − 1 = 1. ✓
STEP Assume Σ_{i≤k} i·i! = (k+1)! − 1.
Σ_{i≤k+1} i·i! = [(k+1)! − 1] + (k+1)(k+1)!
= (k+1)!·[1 + (k+1)] − 1
= (k+1)!·(k+2) − 1
= (k+2)! − 1 ← claim at k+1
CONCLUDE Holds for all n ≥ 1. ∎
The move that makes it work is factoring (k+1)! out of both terms, which is available because (k+1)(k+1)! shares it. Recognising (k+1)!(k+2) = (k+2)! is the same kind of target-driven step as before.
Common mistakes
1
Not writing the target before doing the algebraThe claim at k+1 tells you which factorisation to aim for. Without it the step becomes trial and error.
2
Peeling the wrong termThe sum to k+1 splits as the sum to k plus f(k+1). Splitting off the first term instead leaves a sum the hypothesis does not describe.
3
Using the wrong base caseA formula claimed for n ≥ 0 needs n = 0 checked. Starting at 1 leaves the claim unproved exactly where it is most likely to be false.
Check your understanding
✓
Finish when these proofs are mechanical.
Prove Σ_{i=1}^{n} (2i − 1)² = n(2n−1)(2n+1)/3 — the sum of the squares of the odd numbers. Same three moves, slightly heavier algebra, and no new idea required. Then the product Π_{i=2}^{n} (1 − 1/i) = 1/n for n ≥ 2, which is two lines once the last factor is peeled off.
Note: Sums of kth powers have closed forms for every k, given by Faulhaber's formula, and each is a polynomial of degree k+1 in n. Induction verifies any one of them; producing them requires a different technique.