Series Induction
A statistician needs a closed-form expression for $1 + 2 + 3 + \cdots + n$ — the formula $\dfrac{n(n+1)}{2}$ is "obvious" from Gauss's playground trick, but how do we prove it holds for every positive integer? Mathematical induction is the answer, and the technique is mechanical once you internalise the algebra: add the $(k+1)$-th term, then factor the right-hand side until $\dfrac{(k+1)(k+2)}{2}$ pops out.
You want to prove $\displaystyle\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$. Before any factoring — when you assume the formula at $n = k$, what is the very next algebraic move? And what does the right-hand side need to look like at the end for the proof to close?
Every series induction proof rewards two habits: add the next term to both sides of the hypothesis, then factor the RHS to match the target form at $n = k+1$. The target form is exactly what you get by replacing $k$ with $k+1$ in the closed expression — write it down before you start factoring so you know where you are heading.
The add-and-factor strategy: (1) state $S_k = \dots$ as the hypothesis, (2) compute $S_{k+1} = S_k + a_{k+1}$ (add the next term), (3) factor the RHS until it matches the formula evaluated at $k+1$.
Target: $S_{k+1} = \dfrac{(k+1)(k+2)}{2}$ · Found: $\dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+2)}{2}$ ✓
Key facts
- $\displaystyle\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$
- $\displaystyle\sum_{i=1}^{n} i^2 = \dfrac{n(n+1)(2n+1)}{6}$
- $\displaystyle\sum_{i=1}^{n} i^3 = \left(\dfrac{n(n+1)}{2}\right)^2 = \dfrac{n^2(n+1)^2}{4}$
- Telescoping idea: if $a_i = b_i - b_{i-1}$, then $\sum a_i = b_n - b_0$
Concepts
- Why $S_{k+1} = S_k + a_{k+1}$ is the engine of the inductive step
- How factoring $(k+1)$ from the algebraic expression collapses it to the target
- Why writing the target form before factoring saves you from blind algebra
Skills
- Prove summation identities by induction with clean factoring
- Identify the $(k+1)$-th term and the target form before factoring
- Recognise telescoping sums and use them to verify induction targets
Every series induction problem follows the same four-step skeleton:
- Base case. Verify $P(1)$ — substitute $n=1$ into both LHS and RHS, confirm they match.
- Hypothesis. Assume $P(k)$: $S_k = $ closed-form expression in $k$.
- Step. Compute $S_{k+1} = S_k + a_{k+1}$; factor RHS until it matches the formula at $n = k+1$.
- Conclude. "By induction, $P(n)$ holds for all integers $n \geq 1$."
Worked through the hook — prove $\displaystyle\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$:
- Base ($n=1$): LHS $= 1$; RHS $= \dfrac{1 \cdot 2}{2} = 1$. True.
- Hypothesis: Assume $1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$.
- Step: Target form (replace $k$ with $k+1$): $\dfrac{(k+1)(k+2)}{2}$.
$S_{k+1} = S_k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = (k+1)\left[\dfrac{k}{2} + 1\right] = (k+1) \cdot \dfrac{k+2}{2} = \dfrac{(k+1)(k+2)}{2}$. ✓ - By induction, the formula holds for all $n \geq 1$. $\blacksquare$
Four steps: base, hypothesis, step ($+a_{k+1}$ and factor), conclude · Always write the target form (formula at $n=k+1$) before factoring · $\sum i = \frac{n(n+1)}{2}$: factor $(k+1)$ then simplify $\left[\frac{k}{2}+1\right] = \frac{k+2}{2}$ · Closing line: "by induction, $P(n)$ true for all integers $n \geq 1$"
Pause — copy the series induction four steps (base, hypothesis, $+a_{k+1}$ and factor, conclude) and the closing phrase "by induction, $P(n)$ true for all $n \geq 1$" into your book.
Quick check: In the inductive step for $\sum_{i=1}^{n} i^2 = \dfrac{n(n+1)(2n+1)}{6}$, after adding $(k+1)^2$ to both sides, what is the target form you need to factor towards?
We just saw that the series induction step adds $a_{k+1}$ to both sides and factors $(k+1)$ from the numerator to match the formula at $n = k+1$. That raises a question: is there a non-inductive way to sum certain series, and when is it cleaner? This card answers it → telescoping sums $\sum(b_i - b_{i-1}) = b_n - b_0$, where partial fractions first convert the summand.
If you can write the $i$-th term as a difference $a_i = b_i - b_{i-1}$, the sum collapses: $\sum_{i=1}^{n}(b_i - b_{i-1}) = b_n - b_0$. This is called telescoping. It's both a stand-alone proof technique and a useful way to sanity-check an induction target.
Example: Prove $\displaystyle\sum_{i=1}^{n} \dfrac{1}{i(i+1)} = \dfrac{n}{n+1}$.
- Note $\dfrac{1}{i(i+1)} = \dfrac{1}{i} - \dfrac{1}{i+1}$ (partial fractions).
- Then $\sum_{i=1}^{n} \left(\dfrac{1}{i} - \dfrac{1}{i+1}\right) = \left(1 - \dfrac{1}{2}\right) + \left(\dfrac{1}{2} - \dfrac{1}{3}\right) + \cdots + \left(\dfrac{1}{n} - \dfrac{1}{n+1}\right) = 1 - \dfrac{1}{n+1} = \dfrac{n}{n+1}$.
You can also prove this by induction — the step is $S_{k+1} = \dfrac{k}{k+1} + \dfrac{1}{(k+1)(k+2)} = \dfrac{k(k+2) + 1}{(k+1)(k+2)} = \dfrac{k^2 + 2k + 1}{(k+1)(k+2)} = \dfrac{(k+1)^2}{(k+1)(k+2)} = \dfrac{k+1}{k+2}$. ✓
Telescoping: $\sum_{i=1}^{n}(b_i - b_{i-1}) = b_n - b_0$ · $\dfrac{1}{i(i+1)} = \dfrac{1}{i} - \dfrac{1}{i+1}$ — partial fractions before telescoping · $\sum \dfrac{1}{i(i+1)} = \dfrac{n}{n+1}$ — provable by telescoping OR induction · Always write out first 3 and last 2 terms to confirm cancellation pattern
Pause — copy the telescoping identity $\sum_{i=1}^n (b_i - b_{i-1}) = b_n - b_0$, the partial-fraction split $\frac{1}{i(i+1)} = \frac{1}{i} - \frac{1}{i+1}$, and the result $\sum \frac{1}{i(i+1)} = \frac{n}{n+1}$ into your book.
Did you get this? True or false: the inductive step for $\sum_{i=1}^{n}\frac{1}{i(i+1)} = \frac{n}{n+1}$ requires the algebraic simplification $\frac{k(k+2)+1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2}$.
Worked examples · 3 in a row, reveal as you go
Prove by mathematical induction that $\displaystyle\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$ for all positive integers $n$.
Hypothesis: Assume $1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$.
$1 + 2 + \cdots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1)$.
Prove by mathematical induction that $\displaystyle\sum_{i=1}^{n} i^2 = \dfrac{n(n+1)(2n+1)}{6}$ for all positive integers $n$.
Hypothesis: Assume $1^2 + 2^2 + \cdots + k^2 = \dfrac{k(k+1)(2k+1)}{6}$.
$S_{k+1} = \dfrac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\left[\dfrac{k(2k+1)}{6} + (k+1)\right] = \dfrac{(k+1)[k(2k+1) + 6(k+1)]}{6}$.
Prove by mathematical induction that $\displaystyle\sum_{i=1}^{n} i^3 = \left(\dfrac{n(n+1)}{2}\right)^2 = \dfrac{n^2(n+1)^2}{4}$ for all positive integers $n$.
Hypothesis: Assume $1^3 + 2^3 + \cdots + k^3 = \dfrac{k^2(k+1)^2}{4}$.
$S_{k+1} = \dfrac{k^2(k+1)^2}{4} + (k+1)^3 = (k+1)^2 \left[\dfrac{k^2}{4} + (k+1)\right] = \dfrac{(k+1)^2[k^2 + 4(k+1)]}{4}$.
Fill the gap: When proving $\sum_{i=1}^{n} i^3 = \frac{n^2(n+1)^2}{4}$ by induction, after factoring $(k+1)^2$ from $\frac{k^2(k+1)^2}{4} + (k+1)^3$, the remaining bracket simplifies to $k^2 + 4(k+1) = (k+)^2$.
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: when proving $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$, factoring $(k+1)$ first gives $\frac{k(k+1)}{2} + (k+1) = (k+1)\left[\frac{k}{2} + 1\right] = (k+1)\cdot \frac{k+2}{2} = \frac{(k+1)(k+2)}{2}$.
Activities · practice with the ideas
Prove by induction that $\displaystyle\sum_{i=1}^{n}(2i - 1) = n^2$ (sum of first $n$ odd numbers).
Prove by induction that $\displaystyle\sum_{i=1}^{n} i(i+1) = \dfrac{n(n+1)(n+2)}{3}$.
Prove by induction that $\displaystyle\sum_{i=1}^{n} \dfrac{1}{i(i+1)} = \dfrac{n}{n+1}$. (Alternatively, prove by telescoping.)
Prove by induction that $\displaystyle\sum_{i=1}^{n} (2i - 1)^2 = \dfrac{n(2n-1)(2n+1)}{3}$ (sum of squares of first $n$ odd numbers).
Use telescoping to evaluate $\displaystyle\sum_{i=1}^{n} \left[\dfrac{1}{i} - \dfrac{1}{i+1}\right]$ — then state the result in closed form and verify it agrees with the formula from drill 3.
Odd one out: Three of these statements about the inductive proof of $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ are correct. Which one is NOT?
Earlier you sketched the inductive step for $\sum i = \dfrac{n(n+1)}{2}$ — what you add, and what target form you need to reach.
You add $(k+1)$ to both sides (it's the next term of the series). The target form is $\dfrac{(k+1)(k+2)}{2}$ — exactly what you get by replacing $n$ with $k+1$ in the formula. The factoring trick is to pull $(k+1)$ out: $\dfrac{k(k+1)}{2} + (k+1) = (k+1) \cdot \dfrac{k+2}{2}$. Writing the target form down before factoring is the single biggest discipline improvement for this style of proof.
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. Prove by mathematical induction that $\displaystyle\sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$ for all positive integers $n$. (2 marks)
Q2. Prove by mathematical induction that $\displaystyle\sum_{i=1}^{n} i^2 = \dfrac{n(n+1)(2n+1)}{6}$ for all positive integers $n$. (3 marks)
Q3. Prove by mathematical induction that $\displaystyle\sum_{i=1}^{n} \dfrac{1}{i(i+1)} = \dfrac{n}{n+1}$ for all positive integers $n$. (3 marks)
Comprehensive answers (click to reveal)
Activity answers:
1. Base $n=1$: $1=1^2$ ✓. Assume $\sum_{i=1}^{k}(2i-1)=k^2$. $S_{k+1}=k^2+(2(k+1)-1)=k^2+2k+1=(k+1)^2$. ∎
2. Base $n=1$: $1\cdot 2=2$, $\frac{1\cdot 2\cdot 3}{3}=2$ ✓. Assume $S_k=\frac{k(k+1)(k+2)}{3}$. $S_{k+1}=\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)=(k+1)(k+2)\left[\frac{k}{3}+1\right]=\frac{(k+1)(k+2)(k+3)}{3}$. ∎
3. Base $n=1$: $\frac{1}{1\cdot 2}=\frac{1}{2}$; $\frac{1}{2}$ ✓. Assume $S_k=\frac{k}{k+1}$. $S_{k+1}=\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}=\frac{k(k+2)+1}{(k+1)(k+2)}=\frac{(k+1)^2}{(k+1)(k+2)}=\frac{k+1}{k+2}$. ∎
4. Base $n=1$: $1^2=1$; $\frac{1\cdot 1\cdot 3}{3}=1$ ✓. Assume $S_k=\frac{k(2k-1)(2k+1)}{3}$. $S_{k+1}=\frac{k(2k-1)(2k+1)}{3}+(2k+1)^2 = (2k+1)\left[\frac{k(2k-1)}{3}+(2k+1)\right] = \frac{(2k+1)[k(2k-1)+3(2k+1)]}{3} = \frac{(2k+1)(2k^2+5k+3)}{3} = \frac{(2k+1)(k+1)(2k+3)}{3} = \frac{(k+1)(2k+1)(2k+3)}{3}$. ∎
5. Telescoping: terms cancel pairwise, leaving $1-\frac{1}{n+1}=\frac{n}{n+1}$. Agrees with drill 3 closed form. ✓
Q1 (2 marks): Base ✓ [1]. Assume; $S_{k+1}=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}$. By induction. [1].
Q2 (3 marks): Base ✓ [1]. Assume; $S_{k+1}=\frac{k(k+1)(2k+1)}{6}+(k+1)^2 = \frac{(k+1)[k(2k+1)+6(k+1)]}{6}$ [1] $= \frac{(k+1)(2k^2+7k+6)}{6}=\frac{(k+1)(k+2)(2k+3)}{6}$. By induction. [1].
Q3 (3 marks): Base ✓ [1]. Assume $S_k=\frac{k}{k+1}$ [1]. $S_{k+1}=\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}=\frac{k(k+2)+1}{(k+1)(k+2)}=\frac{(k+1)^2}{(k+1)(k+2)}=\frac{k+1}{k+2}$. By induction. [1].
Five timed series induction problems. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering series induction questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.