    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:Induction on the number of disks(n) for both the odd and even case:Show correctness for the base case, make the inductive hypothesisfor some n=k and then prove that it is valid when n=k+2. This wouldrequire us to show that the remaining pow(2,k+2)-pow(2,k)=3*pow(2,k)steps ofthe 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 caseInduction 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?
Proof for Iterative Solution of Towers of Hanoi
algorithms;correctness proof