Discrete Structure Question 3

Write a recursive pseudo code for Hanoi Tower problem. Write a recurrence relation for the number of moves of the Hanoi Tower code? Solve the recurrence relation and write its explicit formula (closed form). Show that the solution is optimal (i.e., there is no better way to solve the Hanoi Tower problem)