Help with proof by induction The author generates a Tower of Hanoi and looks at the sequence:
$$1, 3, 7, 15, 31, 63,...$$
He guesses the recurrence relation from the first few terms:
$$H_{n} = 2^{n} - 1$$
Now he wants to prove it using proof by induction:

Base case: For $n = 1$, it's true.
Induction case: Assume for induction that $H_{n - 1} = 2^{n - 1} - 1$, then
$$\begin{align*} H_{n} & = 2H_{n - 1} + 1 \\
& = 2(2^{n - 1} - 1) + 1 \\
& = 2^n - 1\end{align*}
$$

I don't understand the above equation. First he says that $H_{n} = 2^{n} - 1$ and then he changes it to $H_{n} = 2H_{n - 1} + 1$ - I don't get the logic in that.
 A: The recurrence relation is not 
$$
H_{n}=2^{n}-1
$$
but rather 
$$
H_{n}=2H_{n-1}+1
$$
(this comes from the Hanoi problem)
We now guess that the solution to the recurrence is 
$$
H_{n}=2^{n}-1
$$
and show that this is true using induction.
There is the base case that should be clear, our hypothesis would
be $H_{n-1}=2^{n-1}-1$ and we would use it to prove 
$$
H_{n}=2^{n}-1
$$
By using the recurrence relation 
$$
H_{n}=2H_{n-1}+1
$$
and now use the induction hypothesis and set $H_{n-1}=2^{n-1}-1$
and we get 
$$
H_{n}=2(2^{n-1}-1)+1=2^{n}-2+1=2^{n}-1
$$
which is what we wanted to prove
A: I think it stems from the fact that the general algorithm to solve a Tower of Hanoi with $n$ rings is to solve one with $n-1$, to move the base, and then to resolve the $n-1$ tower. For more details: http://www.sparknotes.com/cs/recursion/examples/section6.rhtml or just google around. Since $n-1$ Tower of Hanoi requires $H_{n-1}$ moves, $H_n$ must require $H_{n-1}$ to initially move the $n-1$ rings, plus $1$ move to to move the base ring, and then a further $H_{n-1}$ to move the $n-1$ rings back, for a total of $H_{n-1} + 1 + H_{n-1}=2H_{n-1}+1$
