Help with proof by induction

Question

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.

Answer 1

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

Answer 2

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$