# Details about a Recurrence Relation problem.

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.

-
You just opened my eyes. I didn't realize that $H_n = 2^{n−1} + 2^{n−2} +· · ·+2 + 1$ was a Geometric Series. Looks like I need to go back a few chapters. Thank you! –  Chase May 17 '13 at 18:03
@Chase: You’re welcome! –  Brian M. Scott May 17 '13 at 18:04