Induction

This has to be the nicest way that I know to explain the mathematical proof process called induction. It is elegant, simple to understand, and utterly preposterous!

Think about this for a moment: I propose that we should prove, you and I, that the number of people who have shaken hands an odd number times is even. That is, for all people, since the beginning of time, everyone, all over the world, including you.

Ridiculous? Well, of course ridiculous! You yourself for example have shaken hands with lots of people. Often. Even very often. There is no way you can know how often you have done this. So how could you know whether you had done it an odd or an even number of times, let alone all the other people that ever were? Clearly, you couldn't.

Nevertheless we can prove the statement I proposed above. Its not even difficult, if you don't try to read too fast!

At any point in time, today say, right now, the number of times you have shaken someone's hand is either even or odd. There is no other possibility. Similarly for everyone else.

So if we take all the people there ever were, at a particular moment in time when no one is shaking hands, we can put each person into one of two groups. In one group we put all the people who have shaken hands an even number of times, and into the other group we put the people who have shaken hands an odd number of times. Lets call the first group the even group, so the people in it are called the even people. Evidently, the other group is the odd group, full of odd people.

Now lets think about how this changes when two people shake hands. There are not too many possibilities. Both people may be odd, or both may be even, or they may be one odd and one even. What can happen?

a) If both are odd people, they both change to even.

b) If both are even, they both become odd

c) If one is odd and one is even, they swap types, but remain one odd, one even.

And what has happened to the membership of the groups? In case a), the odd group has lost 2 members and the even group has gained 2. In case b) , the odd group has gained 2 members while the even group has lost two members. In case c), the groups stay the same size.

We have no idea of how many people there are in each group. But notice that, although handshaking causes people to move between groups, the groups either do not change size or change by two. Which is to say if the group has an odd number of people in it, handshaking will not make it even, And similarly, if the group has an even number of people in it, then again handshaking will not make it odd.

But lets look more closely at the odd group The only way to enter the group is to shake someone's hand. It is also the only way to leave the group. There was a time when no-one had yet shaken anyone's hand. The odd group was empty until that first handshake. But at the first handshake, the odd group acquires 2 members. At that point, the number of people who had shaken hands an odd number of times was even.

And we have already seen that once a group is even it will always remain even.

So there you have it - the number of people who have shaken hands an odd number of times is even.

Surprised? Don't you love it!

We are not quite done. There are a few more surprises!

For example, what might you expect about the other group, the people who have shaken hands an even number of times? Perhaps, to balance our original theorem, the number of people who have shaken hands an even number of times might be odd?

The above kind of argument does not work. The size of that group when the proto-hand-shakers started a whole new social trend, was all human beings to date less 2, who could hardly be counted accurately enough to decide whether the group would start off even or odd.

Its actually even more disappointing than that. Even if we split off from the even group the people who have not yet shaken hands, we still cant determine whether our theorem is true. But here is one last try. Would our second theorem have worked after all if babies were always born as twins? Think about it!