On the dynamics of Dominos: an introduction to proof by Induction

Toppling dominos is great fun. You stand them up in a line, and then knock the first one over. As it falls it knocks over the second then the second knocks over the third and before you know it you have a spectacular clacking cascade of falling dominos running across the floor: moments of satisfying joy followed by a big mess to clear up! But how can you be sure that they will do exactly what you want and all fall over? You need to be sure that you place each domino the right distance away. Not too far, not too near, and at the right angle. You have an unspoken rule that tells you that if you've set it up right, and a domino goes over then the next one will too. If you apply this rule for each pair then you can be sure that the whole lot will fall over even if you only topple the first.

The dynamics of Dominos ... looks like induction

What is this discussion of Domino dynamics to do with computer science? What it shows is that if you have a rule that tells you how to go from domino to domino, and you topple domino 1, you can be pretty sure that Domino 123 and any others will also fall over down the line. The neat thing is you can be sure of it without checking every single one separately. Instead you just have to check a couple of things. The same trick can be used to topple facts too - even infinite ones. Imagine that rather than dominos you have mathematics. So let TOPPLES(1) be the fact that the first domino falls over, TOPPLES(2) the next, all the way up to TOPPLES(n) where n is any number. (Mathematicians like n to stand for an arbitrary natural number. That is a whole number, no fractions. It's easy to remember, n stands for natural number). Mathematicians would use P instead of TOPPLES to stand for 'Property' or 'Proposition' as it could be any property not just the fact that a domino topples. We will stick with TOPPLES for now though.

What we want to prove is that if for some domino pair (or as we'll see pair of facts) in the chain, when the first of the pair of dominos falls over, the next does too. Mathematically speaking when domino n=k goes over (ie TOPPLES(k) ) then the domino at n=k+1 also falls (ie TOPPLES(k+1)).

As we will see mathematical proof is a really useful thing to be able to do. It means you can be sure something will happen without having to work out every single possibility. It's a real time saver, but needs a bit of hard thinking to get the idea. So with our dominos in mind, let's have a go at proof by induction.

Toppling the maths

This approach of finding a mathematical way to prove that all our dominos fall, i.e. that our mathematics is correct all the way up to an arbitrarily big number n, is called proof by induction. So how would we go about it? All a proof is, is a cast iron argument. For a proof by induction there are specific things you have to check.

The first part of the argument

We start with the first step: the first thing to check. We prove that TOPPLES(1) is true i.e. we show that the domino fall has started. The first result is true; we pushed it!

The second part of the argument

Now comes the so called 'Inductive hypothesis': the second thing we have to check. We assume (guess) that TOPPLES(k) is true for some number k or other (we don't say which). That is we assume that the kth domino has fallen over, but k could be anywhere in the chain. Now the Inductive step we have to show that if that guess is true then TOPPLES(k+1) must be true too i.e. show that if the kth domino has fallen, then the k+1 domino has also fallen. That follows as long as we are sure we did follow the rule of setting the domino in exactly the right position each time - not too near, not too far.

Gluing the two arguments together

These two parts then mean all the dominos must fall. Why? TOPPLES(1) is true from the first part. Combine that with part two. Our guess was true for TOPPLES(1), so the second part of the argument shows TOPPLES(2) is true. Now we know for sure TOPPLES(2) is true but if so then similarly TOPPLES(3) must be... and so on right to the end. All the dominos will fall.

Enough dominos let's apply this cunning idea to some maths.