Proof of Iterative Solution for Tower of Hanoi Problem So I was exploring the Towers of Hanoi problem on wikipedia, and I came across the iterative solution of:

*

*Make the legal move between pegs A and B (in either direction)

*Make the legal move between pegs A and C (in either direction),

*Make the legal move between pegs B and C (in either direction), repeat until complete

for an even number of disks, and for an odd number of disks:

*

*Make the legal move between pegs A and C (in either direction)

*Make the legal move between pegs A and B (in either direction),

*Make the legal move between pegs B and C (in either direction), repeat until complete.

Why does this iterative solution work? I explored a bit further and discovered that if you continue this set of instructions even when the disks are all on the right pole, the disks will eventually end up in a pile in the middle pole. Why does this happen?
 A: If you're interested, I explain how to solve the Tower of Hanoi (plus induction proofs) in this video.
The Iterative Solution basically relies on the principle of induction. If you know how to move a tower with $n-1$ pieces then you can figure out how to move a tower with $n$ pieces. The solution is basically

*

*Move $n-1$ pieces from pole A to pole C

*Move the remaining disk on pole A to pole B

*Move the $n-1$ tower you left on pole C back on top of pole B

Of course step 1) is much more involved than the other steps! Let's unroll step 1) and see what patterns we notice.

*

*Move the $n-2$ pieces from pole A to pole B

*Move the $n-1$ disk that's left on pole A to pole C

*Move the $n-2$ tower from pole B onto pole C

*Move the remaining disk on pole A to pole B

*Move the $n-1$ tower you left on pole C back on top of pole B

Aside from step 1), the other steps involve moving a single disk (the only legal move) at a time between the poles in a pattern indicated by the iterative solution. This pattern is
$$
A\rightarrow B\\
A\rightarrow C\\
B\rightarrow C\\
A\rightarrow B\\
C\rightarrow A\\
C\rightarrow B
$$
If we completely unroll step 1), then we see that the full move sequence for solving the Towers of Hanoi is just repeating this pattern of $6$ steps over and over until we are done. Of course, if we want the tower to end up on a specific pole, we may have to reorder the $6$ steps depending on if the initial tower has an even or an odd number of disks.
