Visual walkthrough — Strong induction

We use only these ideas, and we will build each one before using it:

• an integer $n$ — a whole number like $2,3,4,\dots$;
• a statement $P(n)$ — a claim that is either true or false for each $n$ (e.g. "$n$ is a product of primes");
• $\ge$ means "greater than or equal to"; $<$ means "strictly less than".

---

Step 1 — What "a statement for every number" even looks like

WHAT. Line up the integers starting from some smallest one, $n_0$ (read: "$n$-naught", the starting number). Above each integer we place a lamp. Lamp $n$ is lit if the statement $P(n)$ is true, and dark if we have not yet shown it.

WHY. Before proving anything we need a picture of the goal: we want every lamp lit, all the way to infinity. Ordinary and strong induction are just two different strategies for lighting them all.

PICTURE. Below, the row of lamps sits above the number line. Right now only the very first lamp $n_0$ is lit — that is all we will get "for free".

---

Step 2 — Ordinary induction: each lamp lights the next one

WHAT. Ordinary induction gives you exactly two tools:

1. a base case — lamp $n_0$ is lit;
2. a single-step rule — a wire from each lamp to the one immediately after it: "if lamp $n$ is lit, then lamp $n+1$ lights."

WHY. This is the classic domino chain. Because each wire reaches forward by exactly $1$, one push at $n_0$ cascades forever — but only if every lamp truly depends on just its single predecessor.

$$\underset{\text{this lamp is lit}}{\underbrace{P(n)}}\Rightarrow \underset{\text{so the next lights}}{\underbrace{P(n+1)}}$$

Here the left term is the assumption (one lamp), the arrow is the wire, the right term is the conclusion (the next lamp).

PICTURE. Short green wires, each spanning a single gap. Watch how the "lit" wave rolls right, one lamp at a time.

---

Step 3 — Why we need to reach further back

WHAT. Some statements are wired to several earlier lamps at once. In Prime Factorisation, to show $n=a\times b$ factors into primes, you need lamps $a$ and $b$ lit — and $a,b$ can be anywhere below $n$, not just at $n-1$.

WHY. A single forward wire cannot deliver this. We want a rule whose input is "every lamp below $n$ is lit," so that whichever earlier lamps we happen to need are guaranteed available.

PICTURE. Long coral wires fan out from all earlier lamps into lamp $n$. Compare with Step 2's lone short wire.

---

Step 4 — The trick: bundle the history into ONE lamp $Q$

WHAT. We invent a new row of lamps, one per integer, but a $Q$-lamp lights only when a whole block of $P$-lamps is lit:

$$Q(n):\underset{\text{every }P\text{-lamp from the start up to and including }n}{\underbrace{P(n_0),P(n_0+1),\dots ,P(n)}}\text{are ALL lit.}$$

WHY. This is the master move. Ordinary induction only understands single-step wires. So we repackage "all of the history" into a single $Q$-lamp. Then a one-step wire on the $Q$-row secretly carries all the history on the $P$-row. Note $k\le n$ here (including $n$) — different from Step 3's strict $<$ — because $Q(n)$ records everything up to and including $n$.

PICTURE. Each coral $Q$-lamp sits over a bracket hugging all the $P$-lamps it summarises. Lighting $Q(n)$ means the entire bracket underneath is lit.

---

Step 5 — Base of $Q$: the first bundle lights for free

WHAT. $Q(n_0)$ says "all $P$-lamps from $n_0$ up to $n_0$ are lit" — that is a bundle of exactly one lamp, namely $P(n_0)$. And $P(n_0)$ is our strong-induction base case, which we assumed true.

WHY. Ordinary induction on the $Q$-row needs its own base case to anchor the chain. We just showed it costs us nothing extra: it is the base case we already have.

$$Q(n_0)\equiv \underset{\text{the single base lamp}}{\underbrace{P(n_0)}}✓$$

PICTURE. The leftmost $Q$-bracket wraps a single lit $P$-lamp. Green check: anchored.

---

Step 6 — Inductive step of $Q$: one short wire carries all the history

WHAT. Assume $Q(n)$ (the whole bundle $P(n_0),\dots ,P(n)$ is lit). Read it a second way: it is exactly the strong hypothesis "$P(k)$ for all $k<n+1$". So the strong-step rule fires and lights $P(n+1)$. Add that freshly-lit lamp to the bundle and you have lit $P(n_0),\dots ,P(n+1)$ — which is $Q(n+1)$.

WHY. This is the whole payoff. A single ordinary-induction wire $Q(n)\Rightarrow Q(n+1)$ on the top row is powered by the many-wire strong rule on the bottom row. We converted "all history" into "one predecessor" without losing anything.

$$\underset{\begin{array}{c}\text{bundle }P(n_0..n)\text{ lit}\\ =\text{strong hypothesis for }n+1\end{array}}{\underbrace{Q(n)}}\stackrel{\text{strong rule}}{\to }\underset{\text{next lamp lights}}{\underbrace{P(n+1)}}\Rightarrow \underset{\text{bigger bundle lit}}{\underbrace{Q(n+1)}}$$

PICTURE. A short green wire on the $Q$-row; underneath, the coral fan of the strong rule doing the real work. The bracket grows by one.

---

Step 7 — Fire ordinary induction on $Q$, and read off $P$

WHAT. The $Q$-row now has a base (Step 5) and a single-step wire (Step 6). That is precisely ordinary induction. So every $Q$-lamp lights. And because each $Q(n)$ contains $P(n)$, every $P$-lamp is lit too.

WHY. We never introduced a new axiom. Strong induction is ordinary induction applied to the bundled statement $Q$ — the parent's central claim, now seen as a picture.

$$\underset{\text{by ordinary induction}}{\underbrace{Q(n)\text{for all }n\ge n_0}}\Rightarrow \underset{\text{since }P(n)\subseteq Q(n)}{\underbrace{P(n)\text{for all }n\ge n_0}}■$$

PICTURE. Both rows fully lit; a dashed arrow drops from each $Q$-lamp to the $P$-lamp it guarantees.

---

Step 8 — Degenerate & edge cases (nothing left uncovered)

WHAT & WHY. Three boundary situations the picture must survive:

1. The very first strong step (vacuous history). At $n=n_0$ there are no lamps strictly below $n_0$. The strong hypothesis "$P(k)$ for all $k<n_0$" is then vacuously true (an empty bundle). That is why $P(n_0)$ must be proved directly as a base — the rule gives nothing to stand on there.
2. Reach-back distance $d>1$. If the step needs $P(n-2)$, then for $n=n_0+1$ the lamp $n_0-1$ doesn't exist. Fix: supply $d$ base cases so every reach-back lands inside the lit base zone.
3. Never assume $k=n$. The bundle in $Q(n)$ that feeds the step is strictly below the lamp being lit; $P(n)$ is the output, never an input. Assuming it is circular.

PICTURE. Left: empty coral bracket at $n_0$ (vacuous). Middle: a two-step wire falling off the left edge unless two bases are pre-lit. Right: a "❌" wire looping a lamp back to itself.

Recall Check yourself

At $n=n_0$, how many lamps are strictly below it? ::: Zero — the strong hypothesis is vacuously true, so the base must be proved directly. If the step uses $P(n-3)$, how many base cases? ::: Three, so the reach-back never leaves the lit base zone. Is $P(n)$ ever an input to its own step? ::: No — the hypothesis is strictly $k<n$.

---

The one-picture summary

WHAT. Everything at once: the bottom $P$-row with its many-wire strong rule, the top $Q$-row with its single-step ordinary wire, the base anchor on the left, and the drop-down arrows recovering every $P$ from every $Q$.

Recall Feynman retelling — the whole walkthrough in plain words

Picture two shelves of lamps. On the bottom shelf each lamp needs help from lots of lamps behind it — that's the awkward "strong" wiring, and plain domino-induction can't handle so many wires. So we build a top shelf: a top lamp lights only when a whole run of bottom lamps behind it is already glowing. Now here's the magic — a top lamp only needs the one top lamp just before it, because that previous top lamp already guarantees the whole run underneath. One neat forward wire on top secretly drags all the messy bottom wires along. The first top lamp lights because the first bottom lamp is our given base. From there ordinary dominoes light the whole top shelf, and every top lamp, once lit, guarantees its bottom lamp underneath. So the entire bottom shelf lights too — no new magic, just clever bundling. And if a bottom lamp reaches back two spots, we simply hand-light two starter lamps so nothing falls off the left edge.

---

Connections

• Strong induction — the parent this walkthrough visualises.
• Mathematical Induction (ordinary) — the engine we run on the bundled statement $Q$.
• Well-Ordering Principle — an equivalent route controlling an entire initial segment.
• Recurrence Relations — where multi-lamp reach-backs come from.
• Prime Factorisation — the flagship "$a,b$ anywhere below $n$" example.
• Sequences & Series — closed forms proved by exactly this scheme.