Proof by Dominoes

Lesson 8 of 11 · 7 min · Free, no account needed

What you will learn

Checking many examples is not a proof: 1, 2, 4, 8, 16 regions, and then 31.
Induction proves a rule for every n with two parts: the base (it works for n = 1) and the step (if it works for n, it works for n + 1).
Like dominoes: the first one falls, each one knocks the next, so they all fall.
A broken step breaks the whole proof, even if it fails only once. Recursion in code works the same way.

Points on a circle, every pair joined by a line.
The regions go 1, 2, 4, 8, 16. How many with 6 points? Drag to your bet.
Add the sixth point.
Watch the count.
Game: domino run. Fix each row so every domino falls.
Fix the problem, then Push. A push that stops early counts against you.
This is proof by induction.
Base: show the rule works for n = 1. The first domino falls.
Step: show that if it works for some n, it also works for n + 1. Each domino knocks the next.
Then it works for every n. This is mathematical induction.
1 + 3 + 5 + ... adds up to a square. See the step.
Drag the orange L around the blue square. Three times.
Build the proof on the dominoes.
Drag a card onto each domino, then Check. The row falls only if the chain holds.
The base starts the chain, the step guarantees each case passes to the next, and together they reach every n. A list of checked cases never reaches all of them.
A famous fake proof says all horses are the same colour.
Tap a domino to see its step. Find the step that fails, then Check.
For 2 horses, leaving out the first gives one horse and leaving out the last gives the other. They don't overlap, so nothing ties their colours together. The step fails from 1 to 2.
In code, a function can call itself.
Step through sum_to(4). Each call waits for a smaller one.
Base plus step proves it for every n.
Your proof is on the first domino. Push it.

Lessons are interactive and need JavaScript. Turn it on to play them.