I am trying to understand Recurrence Relations through the Towers of Hanoi example, and I am having trouble understanding the last step:
If $H_n$ is the number of moves it takes for n rings to be moved from the first peg to the second peg, then:
$H_n = 2H_{n−1} + 1$
$H_n = 2(2H_{n−2} + 1) + 1 = 2^2H_{n−2} + 2 + 1$
$H_n = 2^2(2H_{n−3} + 1) + 2 + 1 = 2^3H_{n−3} + 2^2 + 2 + 1 $
$\vdots$
$H_n = 2^{n−1}H_1 + 2^{n−2} + 2^{n−3} +· · ·+2 + 1$
$H_n = 2^{n−1} + 2^{n−2} +· · ·+2 + 1$
$H_n = 2^n − 1.$
I am having trouble understanding the last two steps. How does one go from this:
$H_n = 2^{n−1} + 2^{n−2} +· · ·+2 + 1$
To this:
$H_n = 2^n − 1$
?
The last few lines contain errors. The line
$$H_n=2^{n-1}H_1+2^{n-2}+2^{n-3}+\ldots+2+1$$
is correct, but the next line is not: since $H_1=1$, it should be
$$H_n=2^{n-1}+2^{n-2}+2^{n-3}+\ldots+2+1\;.$$
Apparently the exponents got dropped down onto the main line of text. This is now the sum of a geometric series:
$$H_n=\sum_{k=0}^{n-1}2^k=\frac{2^n-1}{2-1}=2^n-1\;,$$
and again it appears that an exponent was accidentally dropped down to the main line.