Is it possible to play the Tower of Hanoi with fewer than $2^n-1$ moves? The Tower of Hanoi game consists of three identical upright pegs and n rings all of different diameters that can be stacked over any of the pegs. Initially, all of the rings are stacked around one of the pegs in order of decreasing diameter with the largest ring on the bottom. The object of the game is to transfer all the rings, one at a time, until they are stacked in the same order around another peg, but at no time may any ring be placed above a ring of smaller diameter.
Prove that, for any number of rings, the transfer can be made in exactly $2^n-1$ moves. 
We need to use induction... 
Basis Step
IF we let $n=1$, then the left hand side must be 1 and the right hand side must be one as well. 
$1 = 2^1-1$
$1 = 1$
Induction Step.
If $P(k)$ is true, then we can move $k$ disks in $2^k-1$ moves.
If $P(k+1)$ is true, then we can move $k+1$ disks $2^{k+1}-1$
Let $2^k - 1 $ be the number of moves for $k$ disks. Then,
$2(2^k-1)+1$
Using our induction hypothesis, we have 
$2(2^{k+1}-1)$.
For any $ k \geq 1$, $P(k)$ and $P(k+1)$ is true.
Edit: This isn't right at all... it's just fluff...I need to start over. 
Can the Tower of Hanoi be played in less than $2^n-1$ steps? 
This is where I'm stuck... My guess is that unless you break the rules of the game, then you can't play  in fewer steps. Do I use induction to prove that it's impossible or possible?
 A: Actrually it is impossible to do this, it really need $2^{n}-1$ moves.
We can prove it in the following way:
Let $a_{n}$ be the number of moves to finish a Hanoi with $n$ disks. Now we prove that $a_{n}=2^{n}-1$.


*

*For $n=1$, we just need one move, so $a_{1}=1=2^{1}-1$, equation holds when $n=1$.

*We suppose equation holds when $n=k$, that is to say $a_{k}=2^{k}-1$.
For $n=k+1$,
a) We first need to move the top $k$ disks from pile A to B by using pile C, it costs $2^{k}-1$ moves.
b) Then we need to move the last disk from pile A to C, which just costs one move.
c) At last, we need to move all the $k$ disks from pile B to C by using pile A, it costs another $2^{k}-1$ moves.
Now, we have already finish the game when $n=k+1$.
Let calculate $a_{k+1}$, it will be like this by adding all the moves above
$$a_{k+1}=a_{k}+1+a_{k}=2a_{k}+1=2\left(2^{k}-1\right)+1=2^{k+1}-1.$$
Equation holds when $n=k+1$.
From 1. and 2. we can arrive the conclusion that $a_{n}=2^{n}-1$.
So it is impossible to finish a Hanoi game by using less than $2^{n}-1$ moves.
A: Let's get this started. We want to show that for $n\in\mathbb{N}, n\geq 1$ that $P(n) = 2^n-1$ is the number of moves required to complete the Tower of Hanoi.
Base case: $n=1$
There is only $1$ disc so it only takes $1$ move to get it from the first peg to the last peg and $2^1-1=1$ so $P(1)$ is true.
Inductive hypothesis: Assume for some $k \geq 1$ that $P(k)=2^k-1$ is true. We want to show that $P(k+1)=2^{k+1}-1$ is true.
Start with an initial stack of $k+1$ discs. At this point you need to use the rules of the game to get to a stack with $k$ discs so you can use the inductive hypothesis.

I'm going to let you try to fill in the details at this point. But let's take a look at what happens when $n=2$. With 2 discs on the first peg, we move the top disc to the second peg. Then we move the bottom disc to the third peg. Then we move the top disc from the middle peg to the third peg. This takes $2*(1)+1 = 3$ moves. Note that the $(1)$ represents the times we move the top disc.
