1
$\begingroup$

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$

?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Chase May 17 '13 at 18:03
  • 1
    $\begingroup$ @Chase: You’re welcome! $\endgroup$ – Brian M. Scott May 17 '13 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.