I am confused about the 2 inequalities that lead to the Tower of Hanoi recursion formula: T_n = 2T_n-1 + 1

For T_n >= 2T_n-1 + 1, I can understand. You can be inefficient by shuffling around discs that you shouldn't be.

What I can't follow is the other inequality, T_n <= 2T_n-1 + 1

The reasoning I am reading here (and also in other explanations of this problem, like the "Concrete Mathematics" book by Graham, Knuth and Patashnik) is: "Move n-1, then move 1, then move n-1 again. Maybe there's a shortcut, so T_n could be less than or equal to 2T_n-1 + 1, but in fact there is no shortcut."

How do we know there is no shortcut? Are we really just supposing there is no shortcut? Is solving the recursion equivalent to proving there is no shortcut, thus validating the supposition?

Also, while I understand the concept of solving inequalities, in the real-world example of the Tower of Hanoi, it'seems like they could be translated into English like this:

1. T_n <= 2T_n-1 + 1: It could take less than 2T_n-1 + 1 moves (because there might be a shortcut).

2. T_n >= 2T_n-1 + 1: It could take more than 2T_n-1 + 1 moves (because you can make the wrong move and have to reverse it before going on).

So it could take any number of moves! If we are looking for the minimum number of moves, then I guess we can suppose we will never make the wrong move, and thus it will never take more than 2T_n-1 + 1 moves. But I still don't understand the logic that says it can't take less. And I also sense that reasoning things out like this is not really a correct way to solve an inequality, but the equations are supposed to be modeling real life, so I feel at some point I need to understand it in human language.

Finally, is the lack of a shortcut supposed to be self-evident from "move n-1, then move 1, then move n-1 again". But if that is so, why is the "<=" inequality even introduced in the first place?

Sorry to be so wordy, it's hard to be concise when you are confused. Thanks,

-Brian.

>
>For T_n >= 2T_n-1 + 1, I can understand. You can be inefficient by shuffling around discs that you shouldn't be.

In fact this is the weakest part of the derivation. T_n is the minimum number of moves needed to solve the puzzle with N disks. Therefore shuffling of disks around should not be taken into account in so far as those moves are unnecessary.

>What I can't follow is the
>other inequality, T_n <= 2T_n-1 + 1

>The reasoning I am reading here
>(and also in other explanations
>of this problem, like the
>"Concrete Mathematics" book by Graham,
>Knuth and Patashnik) is: "Move
>n-1, then move 1, then
>move n-1 again. Maybe there's
>a shortcut, so T_n could
>be less than or equal
>to 2T_n-1 + 1, but
>in fact there is no
>shortcut."
>
>How do we know there is
>no shortcut?

It's not important for the "<=" inequality. It's clearly the case where saying more than necessary confuses rather than clarifies the picture. Forget about there not being a shortcut. It's really not important here. That there might be is important.

We have established a pattern for solving the puzzle. Move N-1, move 1, move N-1. Therefore, we are able to solve N disks in at most 2T_n-1 + 1 moves. But T_n is the minimum number needed in that case. Therefore

T_n <= 2T_n-1 + 1.

Period.

>Are we really
>just supposing there is no
>shortcut?

No. The above does not use this assumption.

>Is solving the recursion
>equivalent to proving there is
>no shortcut, thus validating the
>supposition?

No, why?

>Also, while I understand the concept
>of solving inequalities,

We do not solve inequalities here. But we do try getting rid of them. What we solve is an equation A = B. How was it obtained? We showed that A >= B and also that A <= B, which implies the identity A = B.

>in the
>real-world example of the Tower
>of Hanoi, it'seems like
>they could be translated into
>English like this:
>
>1. T_n <= 2T_n-1 + 1:
>It could take less than
>2T_n-1 + 1 moves (because
>there might be a shortcut).

Right.

>2. T_n >= 2T_n-1 + 1: It could take more than 2T_n-1 + 1 moves (because you can make the wrong move and have to reverse it before going on).

No, this is not good. And the fault is probably in my explanation. It's not good because, T_n being the minimum number of moves, there could not possibly be wrong moves that had to be reversed.

The correct reasoning is this. We got

>1. T_n <= 2T_n-1 + 1

as above, because there may be a shortcut. Now it's one of the two: either

(1) T_n < 2T_n-1 + 1

or

(2) T_n = 2T_n-1 + 1.

The former can't be. Why? At some point there bound to be a situation with one stack having N-1 smaller disks, one stack empty, and one stack with a single disk, the biggest one. Unless you reach this configuration, there is no way to move the biggest disk. To reach this situation you need exactly T_n-1 moves. There's no shortcuts, because T_n-1 is the minimum. Then you move that largest disk and forget about it. All you have to do now is move the first N-1 disks, which again takes T_n-1 moves. Therefore (2) is the only possibility.

The reason for arguing towards

>1. T_n <= 2T_n-1 + 1

is the mind set that expects two inequalities A >= B and A <= B in order to prove the identity A = B.

>So it could take any number
>of moves! If we are
>looking for the minimum number

But we do.

>of moves, then I guess
>we can suppose we will
>never make the wrong move,
>and thus it will never
>take more than 2T_n-1 +
>1 moves.

Right.

>But I still
>don't understand the logic that
>says it can't take less.

Does the above help?

>And I also sense that
>reasoning things out like this
>is not really a correct
>way to solve an inequality,

We do not solve inequalities. These are just intermediate steps in deriving an equality.

>but the equations are supposed
>to be modeling real life,
>so I feel at some
>point I need to understand
>it in human language.

Absolutely. Never give up.

>Finally, is the lack of a
>shortcut supposed to be self-evident
>from "move n-1, then move
>1, then move n-1 again".
>But if that is so,
>why is the "<=" inequality
>even introduced in the first
>place?

You probably can. This is how:

We have a working algorithm. The algorithm gives the best possible solution, because the configuration 1/N-1/0 is bound to arise from N/0/0, for otherwise there is no way to move the biggest disk. Since T_n-1 is the minimum for N-1 disk, 2T_n-1 + 1 is the minimum for T_n disks. Therefore,

T_n = 2T_n-1 + 1.

>Sorry to be so wordy, it's
>hard to be concise when
>you are confused.

That's OK.

The problem is that brains work differently. Even the most formal proof must be digested and internalized. The mere fact of its being correct does not help. The best way is to prove things by yourself. Consider what you read as a hint and try to make up as much as needed to make you comfortable. Do not for a moment doubt that even the greatest of us do not err. For example, I do think that mentioning the possibility of shuffling around was misleading.

> Thanks,

Thank you. I am going to reword that page.