Now suppose you had two disks. The obvious answer this time is to move the top disk "out of the way" to the third spindle, then move the bottom disk, then move the smaller disk back on top of it. This takes three steps.
Now suppose you had three disks. You can still do basically what you did for the two-disk case, except that you have a stack of two disks to move out of the way instead of just a single one. But fortunately, you already know how to move a stack of two disks. So all you have to do to move a three-disk stack is to use the two-disk method to move the top two disks out of the way (three steps), move the bottom disk to the final position (one step), and move the top two disks back again (three steps), for a total of seven steps.
Now that you've used the two-disk method to come up with a three-disk method, you can use the three-disk method to come up with a four-disk method in exactly the same way. Then you can use the four-disk method to discover the five-disk method, and so on. In fact, if you keep extending your method to more and more disks, you will eventually reach any number N, using the (N-1)-disk method to define the N-disk method. I will know confirm that with four discs it is possible to get from the start (A) to the finish (B) or (C) in a minimum of 15 moves.
I now know that it is possible to move a tower of 4 discs in a minimum of 15 moves. I will know find the least amount of moves required to complete the game when you start with a tower of 5 discs.
I now know that it is possible to move a tower of 5 discs in a minimum of 31 moves. I now have 5 results and will put together a table of results.
Table of Results
2 4 8 16
From the bottom row of differences I can see that the previous term doubled gives the next term in the sequence. Therefore I predict that the next difference would be 32 for a tower of 6 discs (see results table) giving the number of moves as 63 also I can see that the previous number of moves multiplied by 2 plus 1 gives the next number of moves e.g.
1 x 2 + 1 = 3
3 x 2 + 1 = 7
7 x 2 + 1 = 15
15 x 2 + 1 = 31
31 x 2 + 1 = 63
So I can now construct a formula:
The nth term = the previous term doubled, plus one
or
Tn = 2Tn-1 + 1
eg. 1 Tower 2 x 0 +1 = 1
2 Towers 2 x 1 +1 = 3
3 Towers 2 x 3 +1 = 7
4 Towers 2 x 7 +1 = 15
5 Towers 2 x 15 +1 = 31
6 Towers 2 x 31 +1 = 63
7 Towers 2 x 63 +1 = 127
8 Towers 2 x 127 +1 = 255
9 Towers 2 x 255 +1 = 511
10 Towers 2 x 511 +1 = 1023
