Adapted Towers of Hanoi from Concrete Mathematics - number of arrangements
Solution 1:
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.