Our final example is the well known Hanoi Towers puzzle.

In this puzzle, we're given three sticks.

Two of them are initially empty.

On the first stick, we have n discs,

sorted by size as shown here on the slide.

Our goal is to move all n discs to some other stick,

to one of the two empty sticks.

This would be easy if not given two constraints.

First of all, we are allowed to move only one disc at a time, and naturally we need

to take the top most disc from one stick, and to put it to some other stick, right?

And also we are not allowed to put a larger disc onto a smaller disc, okay?

So the question is whether it is possible for, and if it is possible,

then for which values of n this is possible, okay?

So it is known to be possible for every value of n.

At the same time, it is not clear at this point how can we be sure

that it is possible for every possible value of n.

We can check that it is possible for one, for two, for three, for four, and so on.

But it is not so clear how to ensure that just for

every even very huge number, it is always possible.

And of course, we are going to use recursion again

to show how to do this for every possible value of n.

For this, we will first explain that it is possible when n is equal to 1,

and then we will show that if it is possible for n minus 1, for example,

then it is possible for n.

This will ensure that, if it is possible for one, then it is possible for two.

If it is possible for two, then it is possible for three.

If it is possible for three, then it is possible for four, and so on.

So our goal is basically to show that it is possible in the beginning,

when n is equal to 1.

And then we need to show some generic procedure of building a solution for

n discs using a recursive solution for n minus 1 discs, okay?

So let's start.

So the simplest possible case is indeed when there is just one disc.

So in this case, n is equal to 1, and

our goal is to move this disc to some other place, to some other stick,

and of course it is very easy to do this so we just move it to another stick.

Now let's also consider two discs just to get a feeling of how

to solve this problem.

Now in this case, we first move the smallest disc.

So we move it to this stick, then we move the larger disc to another stick.

And finally, we move the smaller one onto larger one, right?

So for two discs, it is also possible.

Now let's consider a general case, where we have n discs.

And let's focus on the larger discs, on the large disc, I'm sorry.

So what is the condition under which we can move it?

So first of all, if we are moving the large disc,

this actually means that all the remaining n minus 1

discs are already on some other stick.

So probably a part of them are on one disc, and

all the remaining of them on the third stick.

I'm sorry.

So if we are moving this large disc, so for which stick we can move it?

So I'm claiming that the only stick for

which we can move it is the empty stick, right?

Because if there are any discs on this stick then we will be allayed the rules.

If there is at least one stick, at least one disc, I'm sorry, on this stick then by

moving the largest disc to this stick, we will put a larger disc onto a smaller one.

So this means that when we are moving the largest disc,

we should move it to an empty stick.

Which in turn means that all the other discs at this point

should be put to the same stick.

And since we know that all the discs are always in increasing order,

we know that at this point, all the other discs should be located as follows, right?

So when we are moving the large disc,

all the remaining discs should be at some other stick.

Which means that up to this point, we've moved all other n minus 1 discs.

So we actually solved the problem for n minus 1 discs, right?

And this gives us an idea for a recursive solution.

Because this is essentially the same problem which was solved for

n minus 1 discs, so a recursive solution in this case is the following.

So we first move n minus 1 discs recursively, to some other stick.

So then we will reach the following state.

After this, we move the largest disc, okay?

And then finally we move, once again, the n minus 1 discs.

Again, using a recursive call, okay?

So we know how to do this because we can call the same

procedure with parameter n minus 1.

And this finally gives us the solution, right?

So again, we reduce the problem with parameter n to the problem

with parameter n minus 1.

This problem in turn will be reduced through a problem with parameter

n minus 2, then with n minus 3, and so on.

Until we reach 1, and for 1, we know that it is possible, right?

So essentially, what we've proved is that it is possible for every value of n.

We can consider this for example like this.

We know that it is possible for 1, then it is possible for 2, right?

Then since it is possible for 2, it is also possible for 3, and so on.

So it will be possible for all the numbers.

Or put it otherwise, to solve the problem for n, we need to solve it for n minus 1.

To solve the problem for n minus 1, we need to solve it for n minus 2.

Meaning that if we know how to do this for n minus 2,

then we definitely know how to do this for n minus 1 and so on.

So going backwards, we will reach 1, and for 1, we know that it is possible.

So which actually proves that it is possible,

and what just happened is that actually we have proved that it is

possible by induction, which is a highly related notion to recursion.

So saying very roughly, induction is a mathematical method for

proving something, where recursion is a method of defining something or

a method of implementing something.

Hanoi Towers

What is a Proof?

Meet the Instructors