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.

This should be a simple one but maybe I'm dumb or maybe I'm just tired, but how to prove that

$$n = 1 + 2^1 + 2^2 + \cdots + 2^h$$

is equal to

$$n = 2^{h+1} - 1$$

?

share|improve this question
2  
Find $2n - n$. Solve for $n$. –  ladaghini Aug 10 '12 at 13:06
2  
multiply the first expression by $(2 - 1)$ and expand. A bunch of stuff cancels and gives you the second expression. –  user29743 Aug 10 '12 at 13:19
    
Possibly useful: About balanced and complete binary tree –  MJD Aug 10 '12 at 13:59
    
You can try induction. –  ᴊ ᴀ s ᴏ ɴ Aug 10 '12 at 14:12

2 Answers 2

up vote 6 down vote accepted

Look here:

http://en.wikipedia.org/wiki/Geometric_series#Sum

share|improve this answer
    
Thank you, I didn't think of the geometric series! –  John Smith Aug 10 '12 at 13:15

It’s a straightforward geometric series, as noted by rbm, but there are other ways to see it.

(1) Write it in binary: $2^n$ in binary is a $1$ followed by $n$ zeroes. Thus, in binary you’re adding $$1+10+100+\ldots+1\underbrace{0\dots0}_h=\underbrace{1\dots1}_{h+1}\;.$$ But clearly $\underbrace{1\dots1}_{h+1}+1=1\underbrace{0\dots0}_{h+1}$, which is the binary representation of $2^{h+1}$. Thus, $$1+2^1+2^2+\ldots+2^h=2^{h+1}-1\;.$$

(2) Prove it by induction on $h$. It’s certainly true for $h=0$: $1=2^1-1$. Suppose that for some $h\ge 0$ we have $$1+2^1+2^2+\ldots+2^h=2^{h+1}-1\;.$$ Then

$$\begin{align*} 1+2^1+2^2+\ldots+2^h+2^{h+1}&=\left(1+2^1+2^2+\ldots+2^h\right)+2^{h+1}\\\\ &=\left(2^{h+1}-1\right)+2^{h+1}\\\\ &=2\cdot2^{h+1}-1\\\\ &=2^{(h+1)+1}-1\;, \end{align*}$$

as desired.

share|improve this answer

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.