Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Find $2n - n$. Solve for $n$. – ladaghini Aug 10 '12 at 13:06
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
up vote 6 down vote accepted

Look here:

share|cite|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|cite|improve this answer

Your Answer


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.