# Proof for Iterative Solution of Towers of Hanoi

    1. Calculate the total number of moves required i.e. "pow(2, n)- 1".
Here n is number of disks.
2. If number of disks (i.e. n) is even then interchange destination
pole and auxiliary pole.
3. for i = 1 to total number of moves:
if i%3 == 1:
legal movement of top disk between source pole and
destination pole
if i%3 == 2:
legal movement top disk between source pole and
auxiliary pole
if i%3 == 0:
legal movement top disk between auxiliary pole
and destination pole


This is an iterative solution to the Towers of Hanoi problem. I tried to prove this algorithm through some ways such as:

1. Induction on the number of disks(n) for both the odd and even case: Show correctness for the base case, make the inductive hypothesis for some n=k and then prove that it is valid when n=k+2. This would require us to show that the remaining pow(2,k+2)-pow(2,k)=3*pow(2,k)steps of the algorithm give the correct output for the case n=k+2.However, the number of steps in the inductive extension depends on the parameter k and is itself 3 times more than that in the base case

2. Induction on the number of iterations in the for loop.I tried to show that if disc movements for some k,k+1 and k+2 iterations occur as stated by the algorithm, then the k+3 iteration should execute the same condition as was executed by the k+1 iteration. However, proving by this method seemed long and tedious as the kth iteration can satisfy the first, second or the third condition and we need to prove for both the odd and the even case.

Could you help me out in proving this iterative solution to the Towers of Hanoi problem?