1
$\begingroup$

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

?

$\endgroup$
  • 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$ – A. Chu Aug 10 '12 at 14:12
6
$\begingroup$

Look here:

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, I didn't think of the geometric series! $\endgroup$ – John Smith Aug 10 '12 at 13:15
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.