Wrong/naive inductive hypothesis and tower of hanoi as an example

Question

I am reading about how a wrong formulation of the tower of Hanoi and the inductive hypothesis can lead to a dead-end.
The example I am reading states the following:

The task is to move N discs from a specific pole to another specific pole. Assume there are poles $A$, $B$ and $C$. The base case is that when the number of discs is 0 then no steps are needed to complete the tasks. For the inductive step assume that we can move $n$ discs from pole $A$ to pole $B$ and we are required to show how to move $n + 1$ discs from $A$ to $B$

Then it highlights that this definition is a dead-end since the only 2 ways to use the induction hypothesis as set don't lead anywhere.
Specifically the options are:

1. Move the top $n$ discs from pole $A$ to $B$. After this point all possibilities of using the induction hypothesis have been exhausted since $n$ discs are on pole $B$ and we do not have hypothesis about moving discs from that pole.
2. Move the smallest disc from pole $A$ to $C$. Then move the remaining $n$ discs from $A$ to $B$. Once again we have exhausted all possibilities of using the induction hypothesis, because $n$ discs are now on pole $B$, and we have no hypothesis about moving discs from this pole.

The reasoning for $1$ is clear to me. If we move the top $n$ discs i.e. the $n$ smaller discs to pole $B$ then at some point we would have to move them again since we would need to place the $nth + 1$ remaining largest disc bellow them. And there is no inductive hypothesis for that so I think I get it.

I need help with the second part. How I understand it is we move the smallest disc to pole $C$. Then we use the inductive hypothesis to move the remaining $n$ larger discs from pole $A$ to $B$. (At this part I am not sure how this could happen if pole $C$ is occupied by the smallest disc but I guess it is part of the logic of using induction in proof.)
Then at that state it seems to me that the only thing pending would be to move the smallest disc from $C$ to $B$ and finish the task.
Why does it state that we would need to move the $n$ discs from pole $B$ and that is not possible since we don't have an induction hypothesis?
Am I misunderstanding something about statements on induction here?

Answer 1

You are right to be concerned about the second part.

Your statement of the only thing pending is correct. However, the second part is nonsense since the only sensible inductive hypothesis concerns 'moving n discs from pole A to pole B, assuming that 3 poles are available'.

An added observation

Looking at your queries in the various comments I feel it might be useful to point out that proof by induction and proof by minimal counterexample are logically equivalent but that some of the things you are questioning seem so much clearer w.r.t. the minimal counterexample method.

If you are trying to prove a result then

(1) Assume it is false.

(2) Consider a counterexample which in some well-defined sense is minimal.

(3) Then try to prove the result by whatever means you wish but where, whenever you need to, you can assume the result for anything 'smaller'.

As an example of the benefits of this way of thinking you can see from this that distinctions such as 'strong' and 'weak' induction are just a distracting irrelevance.

Answer 2

The reason that the second leads to a dead end is because having moved the smallest disk to $C$ you can't move the bottom $n$ disks to $B$ because you can't use $C$ to transfer them. If you could, this would work fine. The bottom $n$ disks are on $B$ and you just move the top disk onto them and are done.

Answer 3

You are correct: the author’s explanation of the problem with the second part is rubbish. He should instead have pointed to the problems that you saw:

• The induction hypothesis is incomplete, since it pretty clearly must include a requirement that pole $C$ be available for the disks being transferred from $A$ to $B$.
• If the transfer of the bottom $n$ disks from $A$ to $B$ actually were possible, we clearly could complete the job of transferring the whole stack by moving the smallest disk from $C$ to $B$.

The problem here isn’t really that the induction hypothesis leads to a dead end: it’s that it is too strong and allows a fallacious argument if this problem isn’t noticed in time.