Why is the following statement true in a proof that I'm studying on binary search trees?

Question

I was studying a proof and there was this line:

$\sum_n^h2^n = 1+2+4+ ... +2^{h-1} + 2^{h} = 2^{h+1} -1$ where (n = 0,1,2,...)

It's been a while since I studied series, can someone help me understand why this is the case? I checked with input and it worked. Are they using some property of series or is it something totally obvious that I'm missing?

Thanks in advance!

Answer 1

Hint:

Note the following pattern of the sum: $1+2+4+… 2^{h-1}+2^h$.

One can easily see that the successive terms are multiplied by $2$, the common ratio. Thus, the series is a finite geometric progression with common ratio $r =2$ and starting term $a=1$.

Answer 2

Let $$ \eqalign{ S &= 1 + 2 + 4 + \cdots + 2^h \cr 2S &= 2 + 4 + 8 + \cdots + 2^{h+1} \cr } $$ substracting from the second the first we get $$ S = 2^{h+1} - 1 $$