Tower of Hanoi with Adjacency Requirement: Suppose that
in addition to the requirement that they never move a larger
disk on top of a smaller one, the person who move the disks
of the Tower of Hanoi are also allowed only to move disks
one by one from one pole to an adjacent pole.Assume
poles A and C are at the two ends of the row and pole B is
in the middle. Let:
$a_{n}$ = the minimum number of moves
needed to transfer a tower of n
disks from pole A to pole C
$b_{n}$ = the minimum number of moves
needed to transfer a tower of n
disks from pole A to pole B
and $b_{n}$ = $a_{n-1} + 1 + b_{n-1}$.
Show that $b_{n}$ = 3$b_{n-1} +1$, for all integers $ n\geq 2$
The basis step is easy.
We need to proof that if $b_{n}$ = 3$b_{n-1} +1$, then $b_{n+1}$ = 3$b_{n} +1$.
By the inductive hypothesis:
$b_{n}$ = $a_{n-1} + 1 + b_{n-1}$
$b_{n+1}$ = $a_{n} + 1 + b_{n}$
But $a_{n}$ = $2b_{n}$ because to transfer a tower of n disks from pole A to pole C we need to transfer the tower from pole A to pole B and from pole B to pole C.
By the inductive hypothesis:
$b_{n}$ = $a_{n-1} + 1 + b_{n-1}$
$b_{n+1}$ = $2b_{n} + 1 + b_{n}$
$b_{n+1}$ = $3b_{n} + 1$
My solution is right? This serve as a proof?
Best Answer
I see two problems with your solution. On the one hand, you've made your presentation more complicated than it needs to be. Given the formulas $b_n=a_{n-1}+1+b_{n-1}$ and $a_n=2b_n$ for all $n$, you can dispense with all the references to induction and simply derive
$$b_n=a_{n-1}+1+b_{n-1}=2b_{n-1}+1+b_{n-1}=3b_{n-1}+1$$
directly.
On the other hand, I think you've glossed over a subtlety in the proof. In particular, I don't quite buy the explanation for $a_n=2b_n$. It's clear to me that $a_n\le 2b_n$, because one way to get everything from A to C is to first get everything from A to B and then get everything from B to C, but it's less clear that you have to do it that way. (To be sure, a modicum of thought makes it clear, but that modicum of thought is, in effect, its own induction proof, just not written down.)
What is clear to me is that, when moving $n$ disks from A to C, you've got to move the bottom disk first from A to B and then from B to C. In order to move the bottom disk from A to B, you've got to move everything above it from A to C, which can be done in $a_{n-1}$ moves. Then to move the bottom disk from B to C, you've got to move the other disks from C back to A, which takes another $a_{n-1}$ moves, after which you'll need to move them all back from A to C, requiring yet another $a_{n-1}$ moves, for a total of
$$a_n=a_{n-1}+1+a_{n-1}+1+a_{n-1}=3a_{n-1}+2$$
moves. And now we can do an induction: If $b_n=3b_{n-1}+1$, then
$$\begin{align} b_{n+1}&=a_n+1+b_n\\ &=(3a_{n-1}+2)+1+(3b_{n-1}+1)\\ &=3(a_{n-1}+1+b_{n-1})+1\\ &=3b_n+1 \end{align}$$