MISSION · Algebra
Proof by Induction
Knock the first domino, and make sure each one topples the next
LEVEL 1 · EXPLORE
Make the idea move
Change the controls and watch what happens. Follow your curiosity and see what you notice.
Loading the activity…
LEVEL 2 · LEARN
Unlock the explanation
Open the chapters in any order. Try the examples as you go.
The idea in one sentence
If a statement is true for 1, and being true for any number forces it to be true for the next, then it is true for every whole number — with no infinite checking required.
The dominoes
Set up an infinite line of dominoes. Two things guarantee they all fall:
- The first one is pushed over.
- Each one that falls knocks over the next.
Neither alone is enough. Push the first with a gap further down and the falling stops. Space them perfectly but never push, and nothing happens at all.
Induction is that argument made precise, with the dominoes being statements about \(1, 2, 3, \ldots\)
The two steps
Base case. Show the statement holds for the starting value, usually \(n = 1\). This is normally a one-line calculation, and it is not optional.
Inductive step. Assume the statement holds for some \(n = k\) — this is the inductive hypothesis — and prove it must then hold for \(n = k + 1\).
Conclude: it holds for all \(n\).
A worked example
Claim: \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\).
Base case. For \(n = 1\): the left side is 1, and the right is \(\frac{1 \times 2}{2} = 1\). True.
Inductive step. Assume \(1 + \cdots + k = \frac{k(k+1)}{2}\). Add the next term to both sides:
\[1 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)\]Factor out \((k+1)\):
\[= (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}\]which is the formula with \(k+1\) in place of \(n\). Both steps hold, so the formula is true for every \(n\).
Notice the shape of the step: start from the assumed case, add whatever gets you to the next one, then rearrange until it matches the target. That’s the standard route.
“Assuming what you’re proving”?
The objection everyone raises, and the answer is precise. You are not assuming the statement for all \(n\). You are assuming it for one unspecified \(k\) and deducing it for \(k+1\) — which is a conditional, “if \(k\) then \(k+1\)”, proved outright.
The base case then feeds that conditional an actual truth to start from, and the chain carries it up forever.
Where it’s used
Sum and product formulas, divisibility claims (\(n^3 - n\) is always divisible by 3), inequalities, and the correctness of recursive algorithms — where the inductive step maps exactly onto the recursive call.
Common mix-ups
- Skipping the base case. Without it, a chain of implications starts nowhere. You can “prove” false statements this way.
- Proving \(k+1\) from scratch instead of using the hypothesis. If you never used the assumption, you haven’t done an induction.
- Verifying a few cases and stopping. Any number of examples is not a proof.
- Forgetting to state the conclusion. The two steps together are the argument.
Check yourself
In proving \(2^n > n\) for all \(n \ge 1\), what exactly do you assume and what do you show?
Assume \(2^k > k\) for some \(k \ge 1\). Then \(2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1\), since \(k \ge 1\) — which is the statement for \(k+1\). The base case is \(2^1 = 2 > 1\).
LEVEL 3 · REFLECT
Add this quest to your trail
When you feel ready, mark this idea as explored. You can always come back and try it again.
EXPLORER STRATEGIES