Suppose that in addition to the requirement that they never move a larger disk on top of a smaller one, the priests 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. If $b_n$ is the minimum number of moves needed to transfer a tower of $n$ disks from pole $A$ to pole $B$, then show that $b_k = 3b_{k−1} + 1$ for all integers $k \ge 2$.
My book gives two answers: one is exactly like the one given by Barry Cipra in Proof with induction for a Tower of Hanoi with Adjacency Requirement and the other one is given as
Another solution is to prove by mathematical induction that when a most efficient transfer of $n$ disks from one end pole to the other end pole is performed, at some point all the disks are on the middle pole.
I'll try the inductive step. Consider $k + 1$ disks. Suppose we end up with $k$ disks on the pole $B$ after performing the most efficient moves from one pole to another. Let it be our hypothesis. Then there'll be only one disk left on either $A$ or $C$. This last disk is the smallest one because otherwise we wouldn't be able to stack all $k$ disks on one pole according to the rules. Then we simply move the last disk onto $B$ which we can because both $A$ and $C$ are adjacent to $B$. So $k + 1$ disks end up on $B$. Does this work?
Suppose as induction hypothesis that when a most efficient transfer of $n$ disks from one end pole to the other end pole is performed, at some point all of the disks are on the middle pole. Now start with $n+1$ disks on pole $A$. At some point the largest disk must be moved from pole $A$ to pole $B$. This can happen only when all $n$ of the smaller disks are on pole $C$, so immediately after moving the largest disk for the first time we have it on $B$ and the rest on $C$. At some point after this we must move the largest disk from $B$ to $C$. This can happen only when the other $n$ disks are on $A$. If we moved them from $C$ to $A$ as efficiently as possible, the induction hypothesis ensures that at some point all of them were on $B$.
Suppose that at that point the largest disk was not on $B$. It could have moved only when all of the other disks were on $A$ or on $C$. At that point they had not yet all reached $A$, because at that point the most efficient transfer of them from $C$ to $A$ was still in progress. They were all on $C$ just before the transfer started, but moving the largest disk back to $A$ at that point would clearly have been waste motion, undoing the immediately preceding move of it from $A$ to $B$. If at some point after that they were again all on $C$, that whole sequence of moves could be cut out of the transfer without changing the outcome, contradicting the fact that we were moving the smallest $k$ disks from $C$ to $A$ as efficiently as possible. Thus, at that point all $k+1$ disks were on pole $B$, as claimed.
We can now justify the recurrence. At some point in the transfer of the top $k$ disks from $A$ to $C$, all of them were on $B$, and by hypothesis it takes at least $b_k$ moves to reach that point. It takes at least another $b_k$ moves to get them to $C$, so it takes at least $2b_k$ to get them from $A$ to $C$ (and we know that it can be done in that many moves). Moving the largest disk from $A$ to $B$ takes $1$ move, and then it takes at least another $b_k$ moves to get the other $k$ disks from $C$ to $B$ (and again we know that it can be done in that many moves). This, moving the $k+1$ disks most efficiently from $A$ to $B$ requires $3b_k+1$ moves, and we have the desired recurrence, $b_{k+1}=3b_k+1$.