1. Prove by induction that the minimum possible number of moves needed to solve the towers of Hanoi satisfies the same recurrence as the number of moves used by our recursive solution. 2. Prove by...

1. Prove by induction that the minimum possible number of moves needed to solve the towers of Hanoi satisfies the same recurrence as the number of moves used by our recursive solution.

2. Prove by induction that the recursive program given in the text makes exactly F_n
recursive calls to fibonacci(1) when computing fibonacci(n).