← All Strategies
∞
Strategy 12 of 12Mathematical Induction
The ladder to infinity: one step at a time
All nRecursiveSequences
Prove something holds for infinitely many cases with just two steps. Base case: verify for $n_0$. Inductive step: show that if it holds for $n = k$, it holds for $n = k+1$. Then it holds for all $n \geq n_0$.
When to use it
- →When the statement says 'for every natural number $n$'
- →In closed-form formulas for sums $1+2+\cdots+n$
- →In recursively defined sequences
- →In divisibility results depending on $n$
- →When structure builds step by step
How to think (step by step)
- 1State $P(n)$ precisely: What must hold?
- 2Base case ($n = n_0$): Verify directly
- 3Inductive hypothesis: 'Assume $P(k)$ holds for some $k \geq n_0$'
- 4Inductive step: Use $P(k)$ to prove $P(k+1)$
- 5Conclusion: $P(n)$ holds for all $n \geq n_0$
Practice Problems
Three problems at increasing difficulty — try each before revealing the hint or solution.
📘Basic
Prove by induction that for all \(n \geq 1\): \(\displaystyle\sum_{i=1}^n i = \frac{n(n+1)}{2}\).
📙Intermediate
Prove that for all \(n \geq 1\): \(\displaystyle\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\).
📕Advanced
Prove that \(n\) lines in general position in the plane divide it into exactly \(\frac{n^2+n+2}{2}\) regions.