Towers of Hanoi? Formula question?

Question

I have to write a formula representing the least number of moves possible to move the disks in the Tower of Hanoi to the proper position. With 2 disks, 3 moves are required, 3 disks require 7 moves, 4 disks require 15 moves and 5 disks require 31 moves. How do I go about writing a formula where "n" equals the number of disks and come up with the number of moves required?

Ok, I feel like an idiot now but what does that symbol stand for? As in 2^n what does the ^ stand for? Thanks!

Answer 1

2 disks 3 moves
3 disks 7 moves
4 disks 15 moves
5 disks 31 moves

as n, the number of disks increases by 1, the number of moves increases by 4, then 8, then 16

notice that these are the values of 2^n as you insert consecutive values in for n.

2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16

This guarantees us that 2^n will be in our equation.

The final step is called the correction phase, where we determine what needs to be added or subtracted to make the values exact.

2 disks, 3 moves 2^2 = 4
3 disks, 7 moves 2^3 = 8
4 disks, 15 moves 2^4 = 16
5 disks, 31 moves 2^5 = 32

Notice that to get from 2^n down to the number of moves for n disks, we just need to subtract one from each value of 2^n

So your equation for the number of moves with relation to the number of disks is:

m = 2^n - 1

So 6 disks would be:
m = 2^6 - 1
m = 64 - 1
63 moves

Answer 2

To get you going in the right direction, set up a table
Disks .... Moves ..... Moves more
2................3....................N/A
3.................7...................4
4................15..................8
5................31...................16
So if n is the number of disks>2, each increase in disk to "n" disks= moves for n-1 disks + (2)^(n-1)

Answer 3

2^n and then all of it minus 1 where n is the number of disks.