Principle of Mathematical Induction
Proving infinitely many statements with two finite steps — the falling dominoes of mathematics
- The principle of mathematical induction and the domino intuition behind it.
- The two pillars of every proof: the base case and the inductive step.
- How to state and use the inductive hypothesis correctly — and why it is not circular.
- To prove summation formulae, divisibility results and inequalities cleanly.
- Strong (complete) induction and when you genuinely need it.
- The most common pitfalls that quietly break an otherwise good proof.
The Domino Idea
Suppose you have infinitely many dominoes in a row, and you know two things: the first one falls, and whenever a domino falls it knocks over the next. Then every domino falls — all of them, without you having to push each one. Mathematical induction is exactly this argument made precise: a way to prove a statement \(P(n)\) for every natural number \(n\) using only two finite checks.
The Principle, Stated Precisely
The starting value need not be 1. If \(P(n_0)\) holds and \(P(k)\Rightarrow P(k+1)\) for all \(k\ge n_0\), then \(P(n)\) holds for all \(n\ge n_0\).
Why is this valid rather than a leap of faith? It rests on a basic property of the natural numbers — the well-ordering principle: every non-empty set of natural numbers has a least element. If \(P(n)\) failed somewhere, there would be a smallest failing value, and the inductive step applied just below it would force a contradiction.
The Two-Step Recipe
Every induction proof — whatever it is about — has the same skeleton. Master the skeleton and the rest is algebra.
| Step | What you do |
|---|---|
| 1 · Base case | Verify \(P(n_0)\) directly (usually \(n_0=1\)). |
| 2 · Hypothesis | Assume \(P(k)\) is true for some fixed \(k\ge n_0\). |
| 3 · Inductive step | Using that assumption, prove \(P(k+1)\). |
| 4 · Conclude | By the principle, \(P(n)\) holds for all \(n\ge n_0\). |
Anatomy of a Proof
Take the most familiar identity, the sum of the first \(n\) natural numbers, and watch each step do its job.
Claim. \(P(n): 1+2+\dots+n=\dfrac{n(n+1)}{2}\).
Base. \(P(1)\): LHS \(=1\), RHS \(=\tfrac{1\cdot2}{2}=1\). ✓
Step. Assume \(1+2+\dots+k=\tfrac{k(k+1)}{2}\). Add \((k+1)\) to both sides:
The right side is exactly \(P(k+1)\). Hence by induction the formula holds for all \(n\ge1\). ∎
The inductive step almost always works by building \(P(k+1)\) out of \(P(k)\): peel off the new piece (the \((k+1)\)-th term, an extra factor, one more domino) so the assumed part appears, substitute the hypothesis, then simplify to the target form.
Where Proofs Go Wrong
Induction is reliable, but only when both pillars stand. Three failures account for nearly every broken proof.
Without \(P(n_0)\) the chain has nothing to start it. You can "prove" \(P(k)\Rightarrow P(k+1)\) for a false statement and conclude nothing.
The step must hold for every \(k\ge n_0\). If it secretly needs \(k\ge3\), the early dominoes never connect.
If \(P(k)\) is never invoked in proving \(P(k+1)\), you have proved each case from scratch — fine, but it is not induction, and usually a sign of an error.
Proving Summation Formulae
Sums are the natural home of induction: each step simply adds the next term. These three results recur throughout the course and are worth proving once and remembering forever.
| Sum | Closed form |
|---|---|
| \(\sum_{r=1}^{n} r\) | \(\dfrac{n(n+1)}{2}\) |
| \(\sum_{r=1}^{n} r^{2}\) | \(\dfrac{n(n+1)(2n+1)}{6}\) |
| \(\sum_{r=1}^{n} r^{3}\) | \(\left[\dfrac{n(n+1)}{2}\right]^{2}\) |
Proving Divisibility
To show \(d \mid f(n)\) for all \(n\), the trick in the inductive step is to write \(f(k+1)\) as \(f(k)\) plus a multiple of \(d\). The hypothesis handles the first piece; the visible multiple of \(d\) handles the second.
If \(f(k)=d\cdot m\) (hypothesis) and \(f(k+1)=f(k)+d\cdot t\), then \(f(k+1)=d(m+t)\) — divisible by \(d\). Typical targets: \(n^3-n\) by 6, \(2^{3n}-1\) by 7, \(4^{n}+15n-1\) by 9.
Proving Inequalities
Inequalities take a little more care: in the step you usually chain through an intermediate quantity. From \(P(k)\) you bound \(P(k+1)\) below (or above) by something you can then push past the target.
The cleanest inductive inequality: multiplying the hypothesis by the non-negative factor \((1+x)\) and discarding the leftover \(nx^2\ge0\) yields the next case at once. It underlies many later limit and AM–GM arguments.
When you multiply or add to an inequality, make sure the factor's sign preserves the direction. Discarding a non-negative term weakens a "\(\ge\)" correctly, but discarding it from a "\(\le\)" can break the proof. State explicitly why each estimate goes the way it does.
Strong (Complete) Induction
Sometimes proving \(P(k+1)\) needs more than just \(P(k)\) — it needs several earlier cases, or one far below. Strong induction grants you all of them.
The conclusion is identical to ordinary induction; only the hypothesis is richer — you may assume the statement for all values up to \(k\), not merely at \(k\).
Strategies & Standard Results
A short field guide for the inductive step.
Rewrite \(P(k+1)\) so the left side of the hypothesis is literally visible, then substitute its right side.
Know in advance what \(P(k+1)\) should read; factor toward that form rather than expanding blindly.
Always test the step from \(n_0\) to \(n_0+1\) explicitly — that is where hidden gaps hide.
Putting It to Work
Problem. Prove \(\sum_{r=1}^{n}r^{2}=\dfrac{n(n+1)(2n+1)}{6}\).
Solution. Base \(n=1\): both sides equal 1. Assume it for \(k\); add \((k+1)^2\):
This is the formula at \(k+1\), completing the induction. ∎
Problem. Prove \(1^3+2^3+\dots+n^3=\left[\dfrac{n(n+1)}{2}\right]^{2}\).
Solution. Base \(n=1\): both sides 1. Assume for \(k\) and add \((k+1)^3\):
Problem. Prove that \(2^{3n}-1\) is divisible by 7 for all \(n\ge1\).
Solution. Base \(n=1\): \(2^3-1=7\). ✓ Assume \(2^{3k}-1=7m\). Then
Divisible by 7, so the result holds for all \(n\). ∎
Problem. Prove \(2^{n}>n\) for every \(n\ge1\).
Solution. Base \(n=1\): \(2>1\). ✓ Assume \(2^{k}>k\). Then
Hence \(2^{k+1}>k+1\), and the inequality holds for all \(n\). ∎
Problem. Prove \((1+x)^{n}\ge 1+nx\) for \(x\ge-1\) and \(n\ge1\).
Solution. Base \(n=1\): equality. Assume \((1+x)^{k}\ge1+kx\). Multiply by \((1+x)\ge0\):
since \(kx^2\ge0\). The induction closes. ∎
Problem. A sequence has \(a_1=1,\ a_2=3\) and \(a_{n}=a_{n-1}+2a_{n-2}\). Prove \(a_n=2^{n}-(-1)^{n}\).
Solution. Check \(a_1=2+1=1\)? Indeed \(2^1-(-1)^1=2+1=3\)… adjust: \(a_1=2-(-1)=3\) matches \(a_2\) form, so verify base cases \(a_1,a_2\) against the formula directly, then assume it for all indices up to \(k\):
Both earlier terms were needed — exactly what strong induction supplies. ∎
Chapter Summary
Base case + inductive step ⇒ \(P(n)\) for all \(n\ge n_0\). The dominoes all fall.
Verify \(P(n_0)\); assume \(P(k)\); prove \(P(k+1)\); conclude. Same skeleton every time.
Add the \((k+1)\)-th term to the hypothesis and factor toward the target form.
Write \(f(k+1)=f(k)+\big(\text{multiple of }d\big)\); the hypothesis does the rest.
Chain through an intermediate bound; Bernoulli \((1+x)^n\ge1+nx\) is the model case.
Assume all cases up to \(k\) when one step is not enough — recurrences, factorisations.
Problems
Prove each by induction; state the base case and the step explicitly. Difficulty rises down the list.
- Prove \(1+3+5+\dots+(2n-1)=n^{2}\).
- Prove \(\sum_{r=1}^{n} r(r+1)=\dfrac{n(n+1)(n+2)}{3}\).
- Prove \(\dfrac{1}{1\cdot2}+\dfrac{1}{2\cdot3}+\dots+\dfrac{1}{n(n+1)}=\dfrac{n}{n+1}\).
- Prove that \(n^{3}-n\) is divisible by 6 for all \(n\ge1\).
- Prove that \(4^{n}+15n-1\) is divisible by 9 for all \(n\ge1\).
- Prove \(7^{n}-3^{n}\) is divisible by 4 for all \(n\ge1\).
- Prove \(n!>2^{\,n-1}\) for all \(n\ge3\).
- Prove \(\dfrac{1}{\sqrt1}+\dfrac{1}{\sqrt2}+\dots+\dfrac{1}{\sqrt n}\ge\sqrt n\) for all \(n\ge1\).
- Prove that \(n\) straight lines in general position divide the plane into \(\dfrac{n^2+n+2}{2}\) regions.
- A sequence has \(a_1=2\) and \(a_{n+1}=3a_n+1\). Prove \(a_n=\dfrac{5\cdot3^{\,n-1}-1}{2}\).
- Prove that every integer \(n\ge2\) can be written as a product of primes (use strong induction).
- Find the flaw: "Claim — for all \(n\), any \(n\) people in a room have the same birthday." Identify precisely which step of the induction fails and why.