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

The story so far

So far we have seen that a proof by induction is like toppling dominos. To topple a chain of facts - that a property holds for all natural numbers - we have to show we it holds for the first one (the first domino topples) and that if it holds for one number it will hold for the next (if one domino falls, it guarantees to topple the next one). Together that is enough to be sure that all the dominos topple, and similarly that a property holds always.

Trust me on this one?

Now apply this cunning idea to some maths. I'm going to tell you (propose) that if you add the first n numbers (that's natural numbers like 1, 3 and 567 but no fractions or negative numbers) then you can get the same answer in a quicker way by multiplying and dividing:

1 + 2 + 3 + 4 + ... + n always gives the same answer as n x (n + 1) / 2.

(we are using x for multiply and / for divide.) Do you believe me?

Mathematically this is written

1 + 2 + 3 + 4 + ... + n = n x (n + 1) / 2.

We will refer to this property holding for number n as P(n). This is my proposition. You can check it for yourself. Honest! Out with your calculator. For the first 10 whole numbers (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55) My property says the answer is (10) x (11) / 2 = 55. See I was right. BUT I've said it works for all n, and it's going to take you a long time to check all of those, one by one: your whole life and you still wouldn't finish! So its time to play the domino trick, a proof by induction.

Prove it!

To start we need our Initial step. First check P(1) is true by replacing n by 1 in 1+..+n = n x (n + 1) / 2. This gives: Left hand side of statement is 1 (there is just the one number in the series) Right hand side is (1) x (1+1) / 2 which simplifies to 1 x (2) / 2 and that is just 1. So the two sides are equal and, Yippee, P(1) is true.

Now we need the next domino trick: the Inductive hypothesis. We assume the result is true for n = k, where k is some number. That is we assume that

P(k) : 1 + 2 + 3 + 4 + ... + k = k x (k + 1) / 2

is true at least for the addition up to k for some number k. Let's call this equation H and we will come back to this assumption in a bit. Now what do we do next?

We need the Inductive step. We need to show that it follows from our hypothesis (guess) H, that we can show P(k + 1) is also true. That is we are aiming to show that the same thing holds if we use k+1 in place of n.

P(k+1) : 1 + 2 + 3 + 4 + ... + k + (k+1) = (k+1) x ((k+1) + 1) / 2

Simplifying that, what we want to show is

P(k+1): 1 + 2 + 3 + 4 + .... + k + (k+1) = (k+1) x (k+2) / 2

That's our target (or 'goal'). It being true because H is true is like the second of a pair of dominos falling because the first falls.

From our induction hypothesis, H, above (our assumption that P(k) is true) we have that 1 + 2 + 3 + ... + k = k x (k + 1) / 2. This gives us a substitution to use. We can replace 1 + 2 + 3 + ... + k anywhere we see it by k x (k + 1) / 2. Using this substitution in our goal statement we get a new goal statement:

P(k+1): (k x (k + 1) / 2) + (k+1) = (k+1) x (k+2) / 2

We've just replaced the sum from 1 to k with our hypothesis H. This is the key step in the proof.

Now tidy up the left hand side, that is k x (k + 1) / 2 + (k + 1) by multiplying out the brackets. This gives a new goal of showing

P(k+1): (k x k/2) + k/2 + k + 1 = (k+1) x (k+2) / 2

Now if we add the k to the half a k we get 3k/2 giving a new version of the goal to prove:

P(k+1): (k x k/2) + 3k/2 + 1 = (k+1) x (k+2) / 2

We can multiply out the brackets on the right hand side too. That gives us a goal of

P(k+1): (k x k/2) + 3k/2 + 1 = (k x k/2) + 2k/2 + k/2 + 2/2

Now 2/2 is just 1 and adding 2k/2 and k/2 is 3k/2 so the above is just the same as the goal

P(k+1): (k x k/2) + 3k/2 + 1 = (k x k/2) + 3k/2 + 1

But now both sides are obviously the same - our goal statement has been turned into one that is obviously true. So that means the original goal must be true as we were sure of each step. In other words:

P(k+1): 1 + 2 + 3 + 4 + ... + k + (k+1) = (k+1) x (k+2) / 2

though only if we know the 'fact' that 1 + 2 + 3 + 4 + ... + k = k x (k + 1) / 2 We have shown that P(k+1) is always true if P(k) is true, which is precisely what we want, since we already checked P(1) was true. By the principle of mathematical induction this means that our proposition P(n) is true for any n you want to try. End of proof. Well done.

Induction a tool for software

Mathematical induction is a very powerful tool that is used to prove that computer programs will behave the way they should without having to check every possible run. It is also useful for proving that a program works as quickly as expected (or not). It's part of the Computer Scientist's arsenal of mathematical methods to help develop safer, better software. It is also a core idea behind a completely different sort of programming language as well as theories about what computation actually is. But that is all another story. After all that thinking, it's time to relax. Anyone for a game of dominos?