Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

?

share|improve this question

1 Answer 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.

share|improve this answer
    
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
1  
@Chase: You’re welcome! –  Brian M. Scott May 17 '13 at 18:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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