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$$


  • 2
    $\begingroup$ Find $2n - n$. Solve for $n$. $\endgroup$
    – ladaghini
    Aug 10 '12 at 13:06
  • 2
    $\begingroup$ multiply the first expression by $(2 - 1)$ and expand. A bunch of stuff cancels and gives you the second expression. $\endgroup$
    – user29743
    Aug 10 '12 at 13:19
  • $\begingroup$ Possibly useful: About balanced and complete binary tree $\endgroup$
    – MJD
    Aug 10 '12 at 13:59
  • $\begingroup$ You can try induction. $\endgroup$
    – JSCB
    Aug 10 '12 at 14:12

Look here:


  • $\begingroup$ Thank you, I didn't think of the geometric series! $\endgroup$
    – 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.


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.