Optimal Towers of Hanoi strategy (3 pillars, from pillar A directly to C not allowed) I am working on a exercise where I need to find the number of steps (Tn) for solving the Towers of Hanoi while having three pillars (A, B, C). All disks (n) are placed at pillar A and need to be moved to pillar C. It is not allowed to move a disk from pillar A to pillar C directly, all disks have to pass pillar B.
I don't know where to start, I tried to write down an example for 2 and 3 discs but at four disks I had the idea I was doing a lot more moves than actually needed.
Any help is appreciated,
Thanks!
 A: To move $n$ disks from $A$ to $C$ you need to move  


*

*$n-1$ disks from $A$ to $C$

*disk $n$ from $A$ to $B$

*$n-1$ disks from $C$ to $A$

*disk $n$ from $B$ to $C$

*$n-1$ disks from $A$ to $C$


To move $n$ disks from $C$ to $A$ you need to move  


*

*$n-1$ disks from $C$ to $B$

*disk $n$ from $C$ to $A$

*$n-1$ disks from $B$ to $A$


To move $n$ disks from $A$ to $B$ you need to move  


*

*$n-1$ disks from $A$ to $C$

*disk $n$ from $A$ to $B$

*$n-1$ disks from $C$ to $B$


To move $n$ disks from $B$ to $A$ you need to move  


*

*$n-1$ disks from $B$ to $C$

*disk $n$ from $B$ to $A$

*$n-1$ disks from $C$ to $A$


To move $n$ disks from $B$ to $C$ you need to move  


*

*$n-1$ disks from $B$ to $A$

*disk $n$ from $B$ to $C$

*$n-1$ disks from $A$ to $C$


To move $n$ disks from $C$ to $B$ you need to move  


*

*$n-1$ disks from $C$ to $A$

*disk $n$ from $C$ to $B$

*$n-1$ disks from $A$ to $B$


This translates into six recurrence relations.  For example 
$$m_{AC}(n)=2+2m_{AC}(n-1)+m_{CA}(n-1)$$
and with all six you can then calculate this for $n$ as large as you like. For example (corrected:) $m_{AC}(20)=40424579$.
A: Using Henry’s notation, the system of recurrences is
$$\left\{\begin{align*}
&m_{AC}(n+1)=2m_{AC}(n)+m_{CA}(n)+2\\
&m_{CA}(n+1)=m_{CB}(n)+m_{BA}(n)+1\\
&m_{AB}(n+1)=m_{AC}(n)+m_{CB}(n)+1\\
&m_{BA}(n+1)=m_{BC}(n)+m_{CA}(n)+1\\
&m_{BC}(n+1)=m_{BA}(n)+m_{AC}(n)+1\\
&m_{CB}(n+1)=m_{CA}(n)+m_{AB}(n)+1\;.
\end{align*}\right.$$
Then $$\begin{align*}
m_{CA}(n+1)&=m_{CB}(n)+m_{BA}(n)+1\\
&=2m_{CA}(n-1)+m_{AB}(n-1)+m_{BC}(n-1)+3\\
&=2m_{CA}(n-1)+2m_{AC}(n-2)+m_{CB}(n-2)+m_{BA}(n-2)+5\\
&=2m_{CA}(n-1)+2m_{AC}(n-2)+m_{CA}(n-1)+4\\
&=3m_{CA}(n-1)+2m_{AC}(n-2)+4\;.
\end{align*}$$
On the other hand, $m_{CA}(n)=m_{AC}(n+1)-2m_{AC}(n)-2$, so $$\begin{align*}
m_{CA}(n+1)&=m_{AC}(n+2)-2m_{AC}(n+1)-2\;,\\
m_{CA}(n-1)&=m_{AC}(n)-2m_{AC}(n-1)-2\;,
\end{align*}$$
and hence $$\begin{align*}
m_{AC}(n+2)-2m_{AC}(n+1)-2&=m_{CA}(n+1)\\
&=3m_{CA}(n-1)+2m_{AC}(n-2)+4\\
&=3m_{AC}(n)-6m_{AC}(n-1)+2m_{AC}(n-2)-2\;,
\end{align*}$$
or $$m_{AC}(n+2)=2m_{AC}(n+1)+3m_{AC}(n)-6m_{AC}(n-1)+2m_{AC}(n-2)\;.$$
Finally, shifting indices gives us $$m_{AC}(n)=2m_{AC}(n-1)+3m_{AC}(n-2)-6m_{AC}(n-3)+2m_{AC}(n-4)\;.$$
By direct computation the initial values are $m_{AC}(0)=0$, $m_{AC}(1)=2$, $m_{AC}(2)=7$, and $m_{AC}(3)=19$. The sequence continues $47, 113, 267, 629$ and is not in OEIS.
The auxiliary equation is $x^4-2x^3-3x^2+6x-2=0$, which reduces to $$(x-1)(x^3-x^2-4x+2)=0\;.$$ The cubic factor has three real roots; I didn’t feel like writing down the exact expressions for them, but this cubic equation calculator says that they are approximately $$\begin{align*}&2.34292308277717\;,\\
-&1.81360650264833\;,\text{ and}\\
&0.47068341987116\;.
\end{align*}$$
In the long run the first will dominate, and the sequence will grow by approximately that factor with each increase of one in the number of disks. For the record, $629/267\approx 2.3558$.
