Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi
Let's start with reformulating the two solutions, following Wikipedia. We use A for the source peg, B for the auxiliary peg, and C for the destination peg.

Recursive algorithm


If $n &gt; 1$, recursively move $n-1$ discs from A to B.
Move the $n$th disk from A to C.
If $n &gt; 1$, recursively move $n-1$ discs from B to C.


Iterative algorithm

If $n$ is even, execute repeatedly until done:


Make a legal move between A and B.
Make a legal move between A and C.
Make a legal move between B and C.


If $n$ is odd, execute repeatedly until done:


Make a legal move between A and C.
Make a legal move between A and B.
Make a legal move between B and C.


(We terminate the algorithms whenever there is no legal move.)



We will prove that both algorithms coincide, using the fact that the recursive algorithm makes exactly $2^n-1$ moves, which can easily be proved by induction. The base case is $n = 1$. In this case, the recursive algorithm moves the disk from A to C, and this is also what the iterative algorithm does.

Suppose now that we have proved the claim for $n$. We will prove it for $n+1$. There are two cases to consider, according to the parity of $n$. Suppose first that $n$ is odd.

The first step in the recursive algorithm is to move $n$ discs from A to B. We know that this is the same as running $2^n-1$ steps of the iterative algorithm for odd many disks, with B and C switched. We observe that upon switching B and C, we exactly obtain the iterative algorithm for even many disks. Therefore the first $2^n-1$ moves made by the iterative algorithm coincide with what the recursive algorithm does (this is because at any step there is a move involving one of the first $n$ disks).

Since $2^n-1 \equiv (-1)^n-1 \equiv 1 \pmod{3}$, after executing $2^n-1$ steps, the next step in the iterative algorithm is to make a legal move between A and C, which is exactly what the recursive algorithm does. We can now rephrase the remaining operation of the iterative algorithm as repeatedly executing the following moves:


Make a legal move between B and C.
Make a legal move between A and B.
Make a legal move between A and C.


This is exactly what the iterative algorithm for odd many disks looks like after switching A and B. Therefore just as before, the following $2^n-1$ steps of both algorithms coincide. The same calculation as before shows that the next move to be considered in the iterative algorithm is the one involving A and B, but there are no disks on either of these pegs, so the iterative algorithm stops. This completes the proof for odd $n$.

The proof for even $n$ is very similar. The first $2^n-1$ moves coincide since switching B and C switches the two versions of the iterative algorithm. This time $2^n-1 \equiv 0 \pmod{3}$, so the next move to be considered by the iterative algorithm involves A and C, matching the recursive algorithm. We can rephrase the operation of the iterative algorithm henceforward as repeatedly executing


Make a legal move between A and B.
Make a legal move between B and C.
Make a legal move between A and C.


This is the same as the iterative algorithm for even number of disks with A and B switched, so the following $2^n-1$ moves coincide. The next move to be considered again involves A and B, which is impossible. This completes the proof.