Even if the legend were true, there would be very little to worry about. Consider this: to move one disk is trivial. To move two disks simply requires moving one disk, and then moving the base disk to the unoccupied peg, and moving the first disk on top. Three disks requires performing the previous task (two disks) then moving the base disk and moving the two disks back on top. In this way we can prove that any number of disks can be moved. There are three main steps required to move disks
1.
|
Move the top disks to another peg.
|
2.
|
Move the last disk to the open peg.
|
3.
|
Move the first disks on top of the last disk.
|
So, if we let be the number of steps for disks, then recursively, . Since (trivially), the first few terms generated by this formula are . This is identical to the sequence generated by the non-recursive function for . Thus, with three pegs, any number of disks can be moved from a starting peg to another peg. Why, then, is there nothing to worry about? If the monks made one move every second, it will take them seconds, or about 585 billion years, to finish their appointed task.