Step 2. Move the largest disk from the first post to the to the second post. This requires just I step n-1 Step 3. Recursively move the n-1 disks on the third post over to the second post. Again, Tn-I steps are required 2 Q. This algorithm shows that Tn, the number of steps required to move n disks to a dif- rent post, is at most 2Tn-1+ 1. We can use this fact to compute upper bounds on the number of steps required for various numbers of disks 13≤2·T2 74<2·T3+1 The algorithm described above answers our first question: given sufficient time, the monks will finish their task and end the world. which is a shame. After all that effort theyd probably want to smack a few high-fives and go out for burgers and ice cream, but nope--world's over. 1.2 A Lower bound for towers of hanoi We can not yet compute the exact number of steps that the monks need to move the 64 disks; we can only show an upper bound. Perhaps-having pondered the problem since the beginning of time-the monks have devised a better algorithm In fact, there is no better algorithm, and here is why. At some step, the monks must move the n-th disk from the first post to a different post. For this to happen, the n-1 smaller disks must all be stacked out of the way on the only remaining post. Arranging the n- l smaller disks this way requires at least Tn-1 moves. After the largest disk is moved at least another In-1 moves are required to pile the n- l smaller disks on topRecurrences 3 Step 2. Move the largest disk from the first post to the to the second post. This requires just 1 step. 1 2 . . . ⇒ n n −1 n 1 2 . . . n −1 Step 3. Recursively move the n−1 disks on the third post over to the second post. Again, Tn−1 steps are required. 1 2 . . . ⇒ n n −1 1 2 . . . n This algorithm shows that Tn, the number of steps required to move n disks to a dif￾ferent post, is at most 2Tn−1 + 1. We can use this fact to compute upper bounds on the number of steps required for various numbers of disks: T3 ≤ 2 · T2 + 1 = 7 T4 ≤ 2 · T3 + 1 ≤ 15 The algorithm described above answers our first question: given sufficient time, the monks will finish their task and end the world. (Which is a shame. After all that effort they’d probably want to smack a few high­fives and go out for burgers and ice cream, but nope— world’s over.) 1.2 A Lower Bound for Towers of Hanoi We can not yet compute the exact number of steps that the monks need to move the 64 disks; we can only show an upper bound. Perhaps— having pondered the problem since the beginning of time— the monks have devised a better algorithm. In fact, there is no better algorithm, and here is why. At some step, the monks must move the n­th disk from the first post to a different post. For this to happen, the n − 1 smaller disks must all be stacked out of the way on the only remaining post. Arranging the n − 1 smaller disks this way requires at least Tn−1 moves. After the largest disk is moved, at least another Tn−1 moves are required to pile the n − 1 smaller disks on top