Multiple Dominoes

Intro to Proofs · Axiom Academy

Dominoes That Need More Than One Some proofs can't lean on just the previous case — they need several behind them. That's strong induction. One domino isn't always enough In ordinary induction, a domino falls the instant the one right before it falls — a clean chain, each step leaning on a single predecessor. But some statements aren't built that way. Sometimes the n th case needs to reach back past P(n-1) to several earlier cases at once. Watch what happens when a domino refuses to fall until all of its prerequisites are down. Press play. The wave topples left to right, each ordinary domino falling on the one before it — until it reaches the orange domino, which is wired to three earlier dominoes . It hangs on, even as its immediate neighbor drops, and only falls once every one of its prerequisites has fallen. The orange domino models a case like P(n) that depends on P(n-1) , P(n-3) , and P(n-4) — knowing only the previous case would never knock it over. How far back is each step allowed to reach? Drag the slider to set how many earlier cases each domino is allowed to assume. At 1 , every domino reaches back to just the one before it — that's ordinary induction, the plain chain. Crank it up and each domino draws on a whole stretch of earlier cases at once: . That wider reach is exactly what strong induction grants you. At d = 1 this is ordinary induction; widen d and you're assuming a whole block of prior cases — the hallmark of strong induction.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.