Hanoi's tower min moves Hello everyone how do you calculate hanoi's min moves for n Discs by mathematical induction I found by some tests that the general number should be a_n=2^n-1 but i couldn't prove it for n+1 so i did some research and found a_(n+1)=2a_n+1 why ?
 A: The proof that you can always solve the Towers of Hanoi problem with $n$ discs in $2^n-1$ moves is a simple inductive proof: 
Base: $n=1$. Trivially, you can move the 1 disc in $2^1-1=1$ move
Step: Using the inductive hypotheses that you can move a stack of $n$ discs from one peg to another in $2^n-1$ moves, you can move $n+1$ discs from peg $A$ to peg $C$ by first moving the top stack of $n$ discs from $A$ to $B$ in $2^n-1$ moves, then moving the largest disc from $A$ to $C$, and then moving the stack of $n$ discs from $B$ to $C$ in $2^n-1$ moves, for a total of $2^n-1+1+2^n-1=2\cdot2^n-1=2^{n+1}-1$ moves.
The proof that this is the minimum amount of moves is almost the same:
Base: Clearly the minimum number of moves to move a stack of 1 disc from $A$ to $C$ is 1.
Step: The inductive hypotheses is that the minimum number of moves to move a stack of $n$ discs from one peg to another is $2^n-1$. Now, if you have a stack of $n+1$ discs, the only way for the larger disc to move from $A$ to $C$ is if the other discs are all on peg $B$. So, any solution will first have to move the top$n$ discs from $A$ to $C$, which takes a minimum of $2^n-1$ moves, then move the largest disc from $A$ to $C$, and then move the other $n$ discs from $B$ to $C$ for a minimum of $2^1-1$ moves, so the minimum number of moves to move all $n+1$ discs from $A$ to $C$ is $2^n-1+1+2^n-1=2\cdot2^n-1=2^{n+1}-1$
A: Note that you can't move the last disk unless you have all others on a different pole. By induction this will take you $2^n-1$ moves. Now $1$ more move to move the biggest disk to another pole and $2^n-1$ more moves to return the rest of the disk back. Hence the number is given by:
$$2^n - 1 + 1 + 2^n - 1= 2^{n+1} - 1$$
