4 Explaining the Towers of Hanoi In class you played around with the famous problem: The Towers of Hanoi. In this project, what I would like you to do is explain what you discovered about this problem by preparing a small report about the problem. I will keep things fairly open ended, but here are the main items I will be looking for. 1. I want you to first explain the setup of the problem. What is it we are measuring? In your own words explain what we are looking for. Your goal should be to define the sequence Mn clearly for the reader. You might want to include pictures you can find of this game online. 2. I want you to explain the idea of recursion and finding a pattern. Describe what happens in small cases, and include a table of numbers like you did in class. 3. Give your conjectured recurrence formula. This is something that is suggested by the data, but not yet confirmed. 4. Explain in words why this recurrence formula is true in terms of the disks and the towers. (This is the most important I will want to see that you really understand why this recurrence holds put this in your own words.) Additional Things to Include The above are all things I think most groups talked about in their discussions, but here are a few additional problems: 5. Please answer the question given on the Ch. 7 worksheet about "how long until the world ends." 6. In class we will prove that a closed form expression for Mn is 2" - 1. Show that this explicit formula satisfies your recursive formula from above. 7. The smallest disk moves a lot more than any of the others. Explore how many steps the smallest disk moves in each case. Let S denote how many times the smallest disk must move if there are n disks. Conjecture a recursive formula for S, and then explain why it is correct. (Again I'm looking for a recursive explanation that relates Sn to S-1 and why.