1. The standard Tower of Hanoi puzzle consists of n circular disks of different sizes, each with a hole in the center, and three pegs. The disks are labeled 1,2, ..., n in increasing order of size. Initially all n disks are on one peg, sorted by size, with disk n at the bottom and disk 1 at the top. The goal is to move all n disks to a different peg, by repeatedly moving individual disks. At each step, we are allowed to move the highest disk on any peg to any other peg, subject to the constraint that a larger disk is never placed above a smaller disk. A recursive strategy that solves this problem using exactly 2" 1 moves is well known (and described in the textbook) This question concerns a variant of the Tower of Hanoi that I'll call the Tower of Fibonacci. In this variant, whenever any two disks i-1 and i +1 are adjacent, the intermediate disk i immediately teleports between them; otherwise, the setup, rules, and goal of the puzzle are unchanged. This teleport does not count as a move; on the other hand, the teleport is not optional. For example, the four-disk Tower of Fibonacci can be solved in nine moves (and two teleports, after moves 5 and 8) as follows: L IN an ab d 1 A nl 180 Da (a) Describe a recursive algorithm to solve the Tower of Fibonacci puzzle. Briefly justify why your algorithm is correct. (We don't need a complete formal proof of correctness; just convince us that you know why it works.) (b) How many moves does your algorithm perform, as a function of the number of disks? Prove that your answer is correct. (c) How many teleports does your algorithm induce, as a function of the number of disks? Prove that your answer is correct. For full credit, give exact answers to parts (b) and (c), not just O(bounds. Express your answers to parts (b) and (c) in terms of the Fibonacci numbers, defined as follows: if n=0 Fn={1 if n=1 Fn-1 + Fn-2 otherwise