This week in Algebra II we are studying the Hanoi tower's. Our assignment was to find what type of formula would give the number of moves it would take to solve the puzzle. After using a T-chart (where $x=$number of disks and $y=$ shortest number of moves that gives the solution)I found that
(0 , 0)
(1 , 1)
(2 , 3)
(3 , 7)
(4 , 15)
and
(5 , 31).
Using the information in the T-chart one should be able to find that $y=2^x-1$, however I don't know how to come to this conclusion on my own. My question today is, how do I find this formula with the given T-chart? That is my only question.....(P.S) everything I need to complete the assignment is done so this is more or less of an add on to improve what I know, NOT to get answers.
Hint: Try to connect the solution for $n$ disks to the one for $n-1$ disks, and proceed by induction.