📊 Section 1 -- Interactive Simulation
Controls
Formula
Display
🧩 Section 2 -- The Idea, Step by Step
Stand a long row of dominoes on end and knock over the first one. If you have spaced them so that every domino is close enough to topple the next when it falls, the whole row goes down -- ten dominoes or ten million, it makes no difference. Notice you only ever checked two things: that the first domino falls, and that any falling domino knocks over its neighbour. Mathematical induction is exactly this trick, turned into a way to prove a statement is true for every counting number at once.
Write $P(n)$ for the claim you want to prove about a whole number $n$ -- say "$1+2+\cdots+n=\tfrac{n(n+1)}{2}$". You prove it in two pieces. The base case checks $P(1)$ directly: here $1=\tfrac{1\cdot2}{2}=1$, true. The inductive step shows that whenever $P(k)$ holds, $P(k+1)$ must follow. Assume $1+\cdots+k=\tfrac{k(k+1)}{2}$ and add the next term: $\tfrac{k(k+1)}{2}+(k+1)=(k+1)\left(\tfrac{k}{2}+1\right)=\tfrac{(k+1)(k+2)}{2}$, which is the very same formula with $k+1$ in place of $n$. Base case = first domino; inductive step = each domino topples the next.
Neither piece works alone: the step by itself proves nothing (a row of dominoes nobody pushes), and the base case alone gives only $P(1)$. Together they force $P(n)$ for all $n$. This is equivalent to the well-ordering principle: if the claim failed somewhere, there would be a smallest failing value $n_0$; but $n_0\neq1$ by the base case, and the inductive step turns the true $P(n_0-1)$ into $P(n_0)$ -- a contradiction. Strong induction simply assumes $P(1),P(2),\ldots,P(k)$ all at once to prove $P(k+1)$, which is handy when a case leans on earlier ones (Fibonacci bounds, prime factorization).
Choose the preset "$1+2+\cdots+n$" and drag Current n: watch "Formula LHS" and "Formula RHS" stay equal at every value, with Match? reading Yes -- that equality holding for each new $n$ is the inductive step firing once. Switch the preset to $1^2+2^2+\cdots+n^2$ and confirm the two readouts still track. Then open the Domino Visual and animate: each newly lit domino is the truth being carried one number further down the line.
📐 Section 3 -- Mathematical Induction
If (1) $P(1)$ is true, and (2) $P(k)\Rightarrow P(k+1)$ for all $k\geq1$, then $P(n)$ is true for all $n\in\mathbb{N}$.
Strong induction: assume $P(1),P(2),\ldots,P(k)$ all true to prove $P(k+1)$.
| Step | What to do | Example: $\sum k=n(n+1)/2$ |
|---|---|---|
| Base case | Verify $P(1)$ directly | $1=1\cdot2/2=1$ ✓ |
| Inductive hyp. | Assume $P(k)$ true | $1+\cdots+k=k(k+1)/2$ |
| Inductive step | Prove $P(k+1)$ | Add $(k+1)$: RHS becomes $(k+1)(k+2)/2$ |
| Conclusion | $\forall n\geq1$, $P(n)$ holds | QED |
$n=1$: LHS $=1$. RHS $=1\cdot2/2=1$. Equal ✓. This anchors the chain.
Assume $\sum_{j=1}^k j=k(k+1)/2$. Then $\sum_{j=1}^{k+1}j=k(k+1)/2+(k+1)=(k+1)(k+2)/2$. The last equality: $k(k+1)/2+(k+1)=(k+1)(k/2+1)=(k+1)(k+2)/2$ ✓.
Well-ordering: every non-empty subset of $\mathbb{N}$ has a least element. If $P(n)$ fails for some $n$, there is a smallest such $n_0>1$. By base case $n_0\neq1$. By inductive step $P(n_0-1)$ true $\Rightarrow P(n_0)$ true -- contradiction. So $P(n)$ holds for all $n$.
Claim: $F_n<2^n$. Base: $F_1=1<2$, $F_2=1<4$ ✓. Strong step: assume $F_j<2^j$ for all $j\leq k$. Then $F_{k+1}=F_k+F_{k-1}<2^k+2^{k-1}<2^k+2^k=2^{k+1}$ ✓.
$n=1$: $0=6\cdot0$ ✓. Assume $6\mid k^3-k$. $(k+1)^3-(k+1)=k^3+3k^2+3k+1-k-1=k^3-k+3k^2+3k=k^3-k+3k(k+1)$. Since $6\mid k^3-k$ (hyp.) and $3k(k+1)$ is divisible by 6 (consecutive integers: one even), the sum is divisible by 6 ✓.
Base $n=1$: $1+1=2$ even ✓. Assume $k^2+k$ even. $(k+1)^2+(k+1)=k^2+2k+1+k+1=k^2+k+2(k+1)$. By hypothesis $k^2+k$ is even; $2(k+1)$ is even; sum is even ✓. QED.
❓ Section 4 -- FAQ
Each is essential. Without base case: you might prove "if $P(k)$ then $P(k+1)$" but start nowhere -- like dominos with no first domino knocked over. Without inductive step: you have $P(1)$ but no chain. Classic fallacy: "all horses are the same color" has a correct inductive step but a faulty base case at $n=2$.
Key takeaway: Both required: base case sets the anchor; inductive step provides the chain. Missing either makes the proof invalid.Each n is a domino. The base case knocks over domino 1. The inductive step shows that whenever domino k falls, it knocks over domino k+1. The animation shows this propagation left to right. You can see exactly which domino is currently falling (highlighted) and all fallen dominoes.
Key takeaway: Domino chain: base case = first push. Inductive step = each falling domino knocks next. Entire chain falls.Proving algorithm correctness (loop invariants). Time complexity analysis (recursion trees). Data structure properties (binary trees with n nodes have n-1 edges). Grammar parsing correctness. Cryptographic protocol security proofs. Any recursive definition -- induction is the natural proof technique.
Key takeaway: Algorithm correctness, complexity, tree properties, grammar parsing -- induction is the foundational CS proof method.Claim: all horses in any set of $n$ horses have same color. Base $n=1$: trivially true. Step: given $n+1$ horses $h_1,\ldots,h_{n+1}$: first $n$ same color, last $n$ same color, so all same. The flaw: for $n+1=2$, the two groups $\{h_1\}$ and $\{h_2\}$ have empty intersection -- the "overlap" argument fails. The step breaks at $k=1\to2$.
Key takeaway: All-horses fallacy: inductive step silently requires non-empty overlap, which fails for n=1 to n=2.Base $n=1$: $1=1\cdot2\cdot3/6=1$ ✓. Inductive step: assume true for $k$. Add $(k+1)^2$: $k(k+1)(2k+1)/6+(k+1)^2=(k+1)[k(2k+1)/6+(k+1)]=(k+1)(2k^2+7k+6)/6=(k+1)(k+2)(2k+3)/6$ ✓. Check $n=4$: $1+4+9+16=30=4\cdot5\cdot9/6=30$ ✓.
Key takeaway: For n=4: LHS=1+4+9+16=30, RHS=4*5*9/6=30 confirmed. Inductive step factors as (k+1)(k+2)(2k+3)/6.Mathematical induction is one of Peano's five axioms for the natural numbers: (1) 0 is a natural number; (2) every natural has a successor; (3) no natural has successor 0; (4) distinct naturals have distinct successors; (5) INDUCTION AXIOM: if a set contains 0 and is closed under successor, it contains all naturals. So induction is not a theorem -- it is definitional of what $\mathbb{N}$ means.
Key takeaway: Induction is Peano axiom 5 -- it DEFINES the natural numbers, not a theorem about them.