Proof by Mathematical Induction

In the savannah, lions are starving and merciless. Each one values his own life more than anything else, and is willing to eat another lion if it can. Suddenly a sick zebra falls dead in the middle of the savannah. Will lions come and eat it?

Yes, but once a lion starts feeding, it becomes vulnerable to other lions’ attacks… Also, I should mention that in this particular savannah, lions have high IQs!

Take your time to meditate on this problem…

Let me give you the basics of proof by induction. This should help you with the lion problem.

A Lock Puzzle

Let me start with a classical math joke. Assuming it takes 3 physicists to screw a lightbulb, one holding the lightbulb while the two others rotate the Universe (if you didn’t get it, check my article on space deformation!), how many mathematicians does it take to do the same job?

Just the one. The mathematician hires 3 physicists and thereby reduces the problem to an earlier solved one.

Yes! Just like computer scientists like to use recursion! The idea is to first build up the basics. Then, the key is to find a way to reduce any problem to the basics.

Sure! Let’s consider this following problem by the amazing James Grime on SingingBanana.

James Grime posted a solution, but I’m going to give another solution to this puzzle, which I personally find even more elegant than his! More interestingly, mine involves proof by induction.

Hehe… We’re going to need to be a bit shrewd here. Let me claim that, no matter what moves we do, if we add the first and third numbers, and we subtract the second one, we always obtain a multiple of 3. In other words, $left-middle+right$ is divisible by 3. Let’s call this claim the invariance property. We can prove this by induction!

Come on! I’ve just told you!

Yes! For this combination, we have $left-middle+right=3-3+3=3$. This is a multiple of 3!

Yes!

Well, any combination you can reach is reached with a certain number of moves, right? Now, the combination 3-3-3 corresponds to 0 move, and we want to make sure that no matter what number of moves we do, we can always reduce our problem to the basic case. There are several ways to do so, but to highlight the most common approach to proofs by induction, let’s analyze the recursion property.

The recursion property consists in reducing the case of $n$ moves to cases of strictly smaller numbers of moves. In other words, we need to prove that, provided that the $(n-1)$-move case satisfies the invariance property, the $n$-move case does too.

First, we assume that any combination obtained after $n-1$ moves or less is such that $left-middle+right$ is a multiple of 3. This is known as the recursion hypothesis.

Now, if we take a combination obtained after $n$ moves, then it is reached from a combination obtained after $n-1$ moves, by making another move. The recursion hypothesis tells us that the combination obtained after $n-1$ satisfies the invariance property, that is, $left-middle+right$ is a multiple of 3. Now, if we make the last move, then we’re either adding 1 to the left and middle numbers (and maybe retracting 3 if numbers go to 4) or adding 1 to the middle and right numbers (with the same remark). In either case, overall, we have added a multiple of 3 to the quantity $left-middle+right$. Thus, it is still a multiple of 3.

Yes! The recursion property says that the invariance property for $n$ moves can thus be reduced to the invariance property for $n-1$ moves. But then, these combinations can be reduced to $n-2$, then for $n-3$, and so on… Until…

Precisely! The following figure illustrates this inductive reasoning:

This scheme shows how that the invariance property holds for all numbers of moves. Thus, for all reachable combinations!

An appropriate illustration of this recursion mechanism is the falling of dominos. By making sure that every domino falls, providing that the previous one does, and by making the first domino fall, all will fall eventually:

With this metaphor, proof by induction consists in two steps. First, we need to make sure that the first domino will fall. This corresponds to the basic case. Then, we need to check whether all dominoes are perfectly alined, such that every domino will make the next one fall. This stands for the recursion property.

If we apply this reasoning to James Grime’s puzzle, then you can see that the combination we are trying to achieve, 2-2-1, does not satisfy the invariance property. Indeed $2-2+1=1$, which is not divisible by 3! Thus, it cannot be reached! Hehe, James Grime, you cunning English mathematician…

And, now, we’re back to the lions! I’m going to give the answer. Try to find it yourself before reading it!

Back to the Lions

So, have you figured it out?

Please, stop reading and keep the good thinking!

As I said, you need to apply the reasoning by induction I’ve presented. So, first…

Yes! What happens with 1 lion?

Yes. What happens with 2 lions?

You’re on a roll! Keep it up! What happens with 3 lions?

Are you sure? Let me rephrase my question. Can the 3-lion case be reduced to the 2-lion case?

Bravo! And this reduces the problem to the 2-lion case! Let me recall you that in this 2-lion case, no lion would go and eat the zebra, so the lion who eats the zebra in a 3-lion case is safe! Now, what about the 4-lion case?

There you go! Let me recapitulate, in a 1-lion case, the lion eats the zebra. In a 2-lion case, no lion does. In a 3-lion case, a lion does. In a 4-lion case, no lion does. Do you see the pattern?

Well, we now need to prove it. And we’ll do this by induction.

Yes! So let’s assume your claim to be true for $n-1$ lions, and let’s consider $n$ lions. We need to distinct the cases where $n$ is even or odd.

OK. If $n$ is even and a lion goes and eats the zebra, then he sort of becomes the zebra with $n-1$ lions around. But $n-1$ is then odd, and, according to the recursion hypothesis, he’d get eaten. So, when $n$ is even, no lion goes and eats the zebra!

Then a lion that goes and eats the zebra would be surrounded by $n-1$ lions. Since $n-1$ is now even, he’d be safe. So, when $n$ is odd, one lion does go and eat the zebra! That’s it! We have proven the case of $n$ lion by reducing it to a problem of $n-1$ lions! The recurrence property is satisfied!

Problem solved! Let’s move on to a trickier one.

Now to the Monks

In a monastery, 77 extraordinarily smart monks meet once a day to pray at noon. Although they see each other, they don’t talk nor communicate by any possible means. The monastery also has a strict no-mirror policy. A morning, a curse suddenly strikes the monastery. At least one monk is cursed. Monks know it. Cursed monks have a red dot on their forehead. But each has no idea whether he is cursed. As soon as one finds out he is cursed, for the good of the community, he must commit suicide at 7pm. Nothing occurs during the first 7 days. But on the evening of the 7th day, some monks commit suicide. Why?

So, have you figured it out?

You’re not doing the induction with the right variable!

Think of the simplest case! This is the case where only one monk is struck by the curse.

Exactly! Let’s move on to the 2-cursed-monk case. Let’s call them Albert and Bob. On the first day, each sees another cursed monk. So none commits suicide. But on the next day, both discover that the other cursed monk is still alive and didn’t commit suicide. So…

Yes! Albert thus figures out that there is a cursed monk other than Bob. But he sees none. So it must be himself! Similarly, Bob figures out that he is cursed too. Therefore…

Exactly! So, when there’s one cursed monk, the suicide occurs on the first day. When there are 2, it occurs on the 2nd day.

Prove it!

Yes. So, assume that your claim is true of $n-1$ monks, and prove it for $n$.

Bravo! So, they all commit suicide on the $n$-th day. This proves the recursion property!

The Pencil Conundrum

Now, to wrap up this article, let me finish with a disturbing reasoning. I’m going to prove by induction that no matter how many pencils you have, they are always of the same color!

Wait for the proof! First, the basic case is obviously when you only have one pencil. It’s obviously of the same color of all the pencils I have.

Now, assume I have $n$ pencils. Let me leave one out. Then I have $n-1$ pencils. So I can apply the recursion hypothesis to these $n-1$ pencils, which are thus of the same color. But wait, let me take another pencil out, and pick again the pencil I initially left out. I still have $n-1$ pencils, and, according to the recursion hypothesis, they still are of the same color. Thus, all of them are of the same color! The recursion property is proven!

This is illustrated in the figure below. Now, obviously, there is something wrong in my proof. I challenge you to find it out!

Any luck?

In fact, everything works perfectly for large numbers. But, sometimes in mathematics, like for Poincaré conjecture, the small numbers are the problems… Do you see what I mean?

Exactly! Each subgroup of pencils is of the same color. But, this color is not necessarily the same because there is no pencil belonging to both subgroups! In other words, all the dominoes are well aligned and ready to fall for $n \geq 3$, and even though the first domino does fall, the first domino doesn’t make the second fall. And all the other dominoes won’t fall.

Let’s Sum Up

Proof by induction was one of these essential ideas of logics and mathematics. It’s a very powerful technic, especially in constructive mathematics. I hope I have made you see why. This technic really relies on two aspects: The basic case and the recursion property. This idea is also the basis of recursion algorithms and structures, which I talk about in my article on self-reference.