Four-Pole Tower of Hanoi: Suppose that the Tower of
Hanoi problem has four poles in a row instead of three.
Disks can be transferred one by one from one pole to any
other pole, but at no time may a larger disk be placed on
top of a smaller disk. Let $s_n$ be the minimum number of
moves needed to transfer the entire tower of $n$ disks from
the left-most to the right-most pole.
Show that $s_{k} \leq 2s_{k−2} + 3$ for all integers $k \geq 3$.
Don't know how to start this one.
Best Answer
HINT: In the usual Tower of Hanoi problem, with three poles, we have $s_k\le 2s_{k-1}+1$, because we can accomplish the transfer of $k$ disks by first transferring $k-1$ to the extra pole, then transferring the biggest disk to the target pole, and finally transferring the $k-1$ disks on the extra pole to the target pole.
In order to show that $s_k\le 2s_{k-2}+3$ for $k\ge 3$, you should try to do something similar: come up with an algorithm for transferring $k$ disks that combines two transfers of $k-2$ disks and three single-disk transfers.