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$

?

  • 0
    You can try induction.2012-08-10

2 Answers 2

6

Look here:

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

  • 0
    Thank you, I didn't think of the geometric series!2012-08-10
5

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.