In playing the Tower of Hanoi for a 3 peg with n amount of disk. In order to get the least amount of moves, in class, we derived the formula
M(n) = 2*m(n-1) + 1
M(n)= m(n-1) + 1+ M(n-1)
M(n)= # of moves for n disk. This formula hold true for all n disks on a 3 peg. This formula simple states that you move twice the number of moves made for n-1 disks. Then since we have a extra disks that is the +1 move for the game.
