I'm working through Concrete Mathematics and have some trouble following a proof about the number of steps needed to solve the 3 peg Tower of Hanoi problem.
For reference, this is the relevant text
They make a point about about explaining why $T_n \ge 2T_{n-1} + 1$, but I don't see why this is valid as $T_n$ has been defined as the minimum number of moves, so I don't see
- when $T_n \gt 2T_{n-1} + 1$ is ever a valid solution as you already know $T_n = 2T_{n-1} + 1$ is a valid solution,
- why you can't conclude that $T_n = 2T_{n-1} + 1$ from this part of the proof alone (or, why is the $T_n \le 2T_{n-1} + 1$ part of the proof necessary).
Yes, you already know from part I that $T_n \le 2T_{n-1} + 1$. But, you have to look at part II as a stand-alone argument, i.e. treat it as if you didn't already know that $T_n = 2T_{n-1} + 1$ is a valid solution. So, since part II, by itself merely shows that it is impossible that $T_n < 2T_{n-1} + 1$, part II of the proof merely shows that $T_n \geq 2T_{n-1} + 1$
Good question! Yes, it seems that part II of the proof gives us a recipe that shows that $T_n = 2T_{n-1} + 1$: move the pile that is on top of the largest disk to the peg that is the other one from the target peg , then move the largest disk to its target peg, and finally move the pile on top of that, giving exactly $2T_{n-1} + 1$.
However, what the proof is really saying here, is this. In order to get to the solution, at some point you have to move the largest disk to the target peg. And, a little thought shows that that is only possible when all the other disks are on the 'other' peg, i.e. neither on the peg where the largest disk is, nor the target peg. So, if there is any solution at all, then it will have to involve the following actions, and in that order:
1) First, the $n-1$ pile needs to be moved away from the largest disk. Since they are on the largest disk at the start, that means that you need to move them all ... and they have to end up as a pile, since they all need to be on the 'other' peg in order for the following action to be possible:
2) The largest peg needs to be moved from wherever it is to the target peg
3) Finally, the $n-1$ pile needs to be moved from the other peg to the target peg.
Note that the order is important here .. we can;t somehow save moves by doing things that somehow, at the same time, accomplish what needs to be done for part 1, as well as for part 3. No, first all of part 1) needs to be completed, then part 2) can be done, and only then part 3) can be completed. So, the minimum number of moves for the whole thing is, at a minimum, the minimum number of moves for 1), plus the minimum number of moves for part 2), plus the minimum number of moves for part 3).
OK, but it all still seems so very obvious that you can do part 1) in exactly $T_{n-1}$ moves, and same for part 3), and part 2) should only take 1 move. Right?
Well, think about this: we assumed by inductive hypothesis that moving $n-1$ disks from one peg to another takes $T_{n-1}$ moves where there are no other disks involved. Now, however, we have an extra disk. So: might the presence of this extra disk prevent one to move the pile in $T_{n-1}$ moves? Might the presence of this disk somehow necessarily increase that number of moves of that action (or: possibly prevent this action from being possible at all?) Now, that, of course, is the province of part I of the proof, not part II. And this is why part I of the proof is necessary.
Now, I have to say, the text does not discuss this possibility at all .. which is also why I am actually quite sympathetic to your second question: what is part I of the proof even saying that part II of the proof isn't already pointing out? Well, a proper proof for part I would have to point out that the presence of the extra disk does not in any way hinder the movement of the pile, and that, therefore, moving the pile can indeed still be done in $T_{n-1}$ moves.
Anyway, the point is: part II of the proof only points out that parts 1) and 3) take at least $T_{n-1}$ moves, and it is up to part I of the proof to point out that in fact each can be done in exactly $T_{n-1}$ moves.
Likewise, part II of the proof by itself does not make it clear that part 2) of the necessary actions (moving the largest disk from start to goal post) can be done in exactly 1 step. Of course, it is blatantly obvious that it is possible, as long as action 1) consistent of moving gthe pile to the peg other than both the start and goal peg, but actually I think the text does a decent job here, in pointing out that possible it does take more than 1 move ("we might move the argest disk more than once, if we're not too alert"). Indeed, action 1) never specifies that the pile should go to the other peg ... it just said that it needs to moved so that the largest disk can possibly move itself. And, if you were to move the pile to the goal peg, then you can only move the largest disk to the other peg, and hence it is still not on the goal peg, and so it would take more than 1 move to get the largest disk from the start peg to the goal peg (again, I do agree that the text could have spelled this all out a bit more).
So again, part II of the proof sates that action 2) takes at a minimum 1 move, and we need part I of the proof to point out that we can move the largest disk from start to goal disk in exactly one move.