A less familiar chapter in the Tower of Hanoi's history is its brief relocation of the temple
Question:
A less familiar chapter in the Tower of Hanoi's history is its brief relocation of the temple from Benares to Pisa in the early 13th century. The relocation was organized by the wealthy merchant-mathematician Leonardo Fibonacci, at the request of the Holy Roman Emperor Frederick II, who had heard reports of the temple from soldiers returning from the Crusades. The Towers of Pisa and their attendant monks became famous, helping to establish Pisa as a dominant trading center on the Italian peninsula. Unfortunately, almost as soon as the temple was moved, one of the diamon needles began to lean to one side. To avoid the possibility of the leaning tower falling over from too much use, Fibonacci convinced the priests to adopt a more relaxed rule: Any number of disks on the leaning needle can be moved together to another needle in a single move. It was still forbidden to place a larger disk on top of a smaller disk, and disks had to be moved one at a time onto the leaning needle or between the two vertical needles. Thanks to Fibonacci's new rule, the priests could bring about the end of the universe somewhat faster from Pisa than they could from Benares. Fortunately, the temple was moved from Pisa back to Benares after the newly crowned Pope Gregory IX excommunicated Frederick II, making the local priests less sympathetic to hosting foreign heretics with strange mathematical habits. Soon afterward, a bell tower was erected on the spot where the temple once stood; it too began to lean almost immediately. Describe an algorithm to transfer a stack of n disks from one vertical needle to the other vertical needle, using the smallest possible number of moves. Express the exact number of moves your algorithm performs as a closed-form expression in terms of Fibonacci numbers:
F 0 = 0, F 1 = 1, and F n = F n-1 + F n-2 for all n ? 2.
(Describing the runtime using one or two recurrence relations, including base cases, is worth substantial partial credit.)
Calculus Early Transcendentals
ISBN: 978-0321947345
2nd edition
Authors: William L. Briggs, Lyle Cochran, Bernard Gillett