2 RECURRENT PROBLEMS It's not immediately obvious that the puzzle has a solution,but a little thought (or having seen the problem before)convinces us that it does.Now the question arises:What's the best we can do?That is,how many moves are necessary and sufficient to perform the task? The best way to tackle a question like this is to generalize it a bit.The Tower of Brahma has 64 disks and the Tower of Hanoi has 8;let's consider what happens if there are n disks. One advantage of this generalization is that we can scale the problem down even more.In fact,we'll see repeatedly in this book that it's advanta- geous to Loox ar sMLL cases first.It's easy to see how to transfer a tower that contains only one or two disks.And a small amount of experimentation shows how to transfer a tower of three. The next step in solving the problem is to introduce appropriate notation: NAME AND coNQueR.Let's say that Tn is the minimum number of moves that will transfer n disks from one peg to another under Lucas's rules.Then T is obviously 1,and T2=3. We can also get another piece of data for free,by considering the smallest case of all:Clearly To =0,because no moves at all are needed to transfer a tower of n =0 disks!Smart mathematicians are not ashamed to think small, because general patterns are easier to perceive when the extreme cases are well understood (even when they are trivial). But now let's change our perspective and try to think big;how can we transfer a large tower?Experiments with three disks show that the winning idea is to transfer the top two disks to the middle peg,then move the third, then bring the other two onto it.This gives us a clue for transferring n disks in general:We first transfer the n -1 smallest to a different peg (requiring Tn-1 moves),then move the largest (requiring one move),and finally transfer the n-1 smallest back onto the largest (requiring another Tn-1 moves).Thus we can transfer n disks (for n >0)in at most 2Tn-1+1 moves: Tn 6 2Tn-1+1 for n 0. This formula usesinstead of(='because our construction proves only that 2Tn-1+1 moves suffice;we haven't shown that 2Tn-1+1 moves are necessary.A clever person might be able to think of a shortcut. But is there a better way?Actually no.At some point we must move the Most of the pub- largest disk.When we do,the n-1 smallest must be on a single peg,and it lished“solutions" has taken at least In-1 moves to put them there.We might move the largest to Lucas's problem, like the early one disk more than once,if we're not too alert.But after moving the largest disk of Allardice and for the last time,we must transfer the n-I smallest disks (which must again Fraser fail to ex- be on a single peg)back onto the largest;this too requires Tn-1moves.Hence plain why Tn must be≥2Tn1+1. Tn 3 2Tn-1+1,for n 0.2 RECURRENT PROBLEMS It’s not immediately obvious that the puzzle has a solution, but a little thought (or having seen the problem before) convinces us that it does. Now the question arises: What’s the best we can do? That is, how many moves are necessary and sufficient to perform the task? The best way to tackle a question like this is to generalize it a bit. The Tower of Brahma has 64 disks and the Tower of Hanoi has 8; let’s consider what happens if there are n disks. One advantage of this generalization is that we can scale the problem down even more. In fact, we’ll see repeatedly in this book that it’s advanta￾geous to LOOK AT SMALL CASES first. It’s easy to see how to transfer a tower that contains only one or two disks. And a small amount of experimentation shows how to transfer a tower of three. The next step in solving the problem is to introduce appropriate notation: NAME AND CONQUER. Let’s say that T,, is the minimum number of moves that will transfer n disks from one peg to another under Lucas’s rules. Then Tl is obviously 1, and T2 = 3. We can also get another piece of data for free, by considering the smallest case of all: Clearly TO = 0, because no moves at all are needed to transfer a tower of n = 0 disks! Smart mathematicians are not ashamed to think small, because general patterns are easier to perceive when the extreme cases are well understood (even when they are trivial). But now let’s change our perspective and try to think big; how can we transfer a large tower? Experiments with three disks show that the winning idea is to transfer the top two disks to the middle peg, then move the third, then bring the other two onto it. This gives us a clue for transferring n disks in general: We first transfer the n - 1 smallest to a different peg (requiring T,-l moves), then move the largest (requiring one move), and finally transfer the n- 1 smallest back onto the largest (requiring another Tn..1 moves). Thus we can transfer n disks (for n > 0) in at most 2T,-, + 1 moves: T, 6 2Tn-1 + 1 , for n > 0. This formula uses ‘ < ’ instead of ‘ = ’ because our construction proves only that 2T+1 + 1 moves suffice; we haven’t shown that 2T,_, + 1 moves are necessary. A clever person might be able to think of a shortcut. But is there a better way? Actually no. At some point we must move the largest disk. When we do, the n - 1 smallest must be on a single peg, and it has taken at least T,_, moves to put them there. We might move the largest disk more than once, if we’re not too alert. But after moving the largest disk for the last time, we must transfer the n- 1 smallest disks (which must again be on a single peg) back onto the largest; this too requires T,- 1 moves. Hence Most of the pub￾lished “solutions” to Lucas’s problem, like the early one of Allardice and Fraser [?I, fail to ex￾plain why T,, must be 3 2T,, 1+ 1. Tn 3 2Tn-1 + 1 , for n > 0