This is correct, thought it could be stated a little better, and there is a shorter argument.
To state it better, note that you're really just doing an induction on $n$: you're showing that if the transfer of $n-1$ disks goes through all possible arrangements, then so does the transfer of $n$ disks.
The short argument is simply to count the arrangements, as you did, and note that the optimal sequence of moves never repeats a position. (If it did, it couldn't be optimal.) Thus, it must go through every possible arrangement.
$B(n)$ is the minimum number of moves required to move $2n$ disks subject to the stated constraints, and $A(n)$ is the minimum number required if we require only that no disk ever rest on a smaller disk.
The crucial point is that the solution to part (a) of the problem almost works for part (b): it leaves all of the disks in their original order except the two largest ones, which are reversed. We can avoid this reversal as follows.
- First use the part (a) method to move the top $2(n-1)$ disks from peg A to peg B; this takes $A(n-1)$ moves and leaves the bottom two disks on peg B in the wrong order.
- Then move the two largest disks one at a time to peg C; this takes $2$ moves and leaves them in the wrong order.
- Then use the part (a) method to move the $2(n-1)$ disks on peg B back to peg A; this leaves them in the right order, since it reverses the bottom two a second time.
- Then move the two largest disks one at a time from peg C to peg B; this takes $2$ moves and restores them to their correct order.
- All that remains is to move the $2(n-1)$ disks on peg A to peg B atop the two largest disks; by definition this takes $B(n-1)$ moves.
Putting the pieces together, we see that
$$\begin{align*}
B(n)&=A(n-1)+2+A(n-1)+2+B(n-1)\\
&=B(n-1)+2A(n-1)+4\\
&=B(n-1)+2\left(2^n-2\right)+4\\
&=B(n-1)+2^{n+1}\;,
\end{align*}$$
where the penultimate step uses the closed-form solution $A_n=2^{n+1}-2$ of part (a).
Now we have the first-order recurrence $B(n)=B(n-1)+2^{n+1}$ with $B(1)=3$, which can be solved by ‘unwinding’:
$$\begin{align*}
B(n)&=B(n-1)+2^{n+1}\\
&=B(n-2)+2^n+2^{n+1}\\
&=B(n-3)+2^{n-1}+2^n+2^{n+1}\\
&\;\;\vdots\\
&=B(n-k)+\sum_{i=n+2-k}^{n+1}2^i\\
&\;\;\vdots\\
&=B(1)+\sum_{i=n+2-(n-1)}^{n+1}2^i\\
&=3+\sum_{i=3}^{n+1}2^i\\
&=3+\sum_{i=0}^{n+1}2^i-\sum_{i=0}^22^i\\
&=3+\left(2^{n+2}-1\right)-7\\
&=2^{n+2}-5\;.
\end{align*}$$
If you’re in any doubt about the calculation, you can prove the result by induction on $n$: certainly $B(1)=3=2^{1+2}-5$, and if $B(n)=2^{n+2}-5$, then
$$B(n+1)=B(n)+2^{n+2}=2\cdot 2^{n+2}-5=2^{n+3}-5\;,$$
as desired.
This does not actually show that this procedure gives the minimum possible number of moves, but it does show that the transfer is always possible in $2^{n+2}-5$ moves, and it can be shown that this is the best possible result.
Added: This is going to be a bit informal rather than entirely rigorous.
To see that this is the best possible result, let the two largest disks be $\top$ (on top) and $\bot$ (on the bottom), and let the tower of $2(n-1)$ smaller disks be $T$. At some point we must move $\bot$ to peg B; assuming that we do so directly, rather than by way of peg C, this requires getting $\top$ and $T$ to B. If $m$ is the minimum number of moves needed to accomplish this, we’ll need at least $2m+1$ moves to transfer everything from A to B — more, if $T$ doesn’t end up in the right order. Getting $\top$ and $T$ from A to C requires getting $T$ to B, where it’s out of the way, so that we can move $\top$ from A to C; by definition this requires a minimum of $A(n-1)$ moves. After moving $\top$ to C, we must still move $T$ to C on top of $\top$, so $m=2A(n-1)+1$. Note that this actually leaves the disks in $T$ in the correct order, since we’ve reversed the order of the two bottom disks of $T$ twice while leaving the other pairs alone.
This means that we need at least
$$2m+1=4A(n-1)+3=4\left(2^n-2\right)+3=2^{n+2}-5$$
moves to transfer the entire stack from A to B. We’ve already seen that the task can be accomplished in this many moves, so this is the best possible result.
Note that we now have a second algorithm that also produces the best possible result:
- Move $T$ to B.
- Move $\top$ to C.
- Move $T$ to C atop $\top$.
- Move $\bot$ to B.
- Move $T$ to A.
- Move $\top$ to B atop $\bot$.
- Move $T$ to B atop $\top$.
Best Answer
Step 5 is the same as Step 1. We move the stack of $n−1$ disks in $S_{n−1}$ (legal) steps. This stack move will also use peg 2 in the process, of course, but we don't spell it out as part of this argument. The larger disks below don't affect or interfere with the movement of smaller disks during the stack move.
Thus the recurrence definition of $S_n$ can be established just by adding the number of moves in the 5 steps.
$$S_n = \overbrace {S_{n-1}}^{\text{step 1}}+\overbrace {1}^{\text{step 2}}+\overbrace {S_{n-1}}^{\text{step 3}}+\overbrace {1}^{\text{step 4}}+\overbrace {S_{n-1}}^{\text{step 5}} = 3S_{n-1}+2$$
You could also observe, perhaps, that $S_1=2$.