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

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?

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

• @V.Poghosyan You can accept my answer if it helped you by ticking the green mark on the side.
– user371838
Dec 15, 2017 at 5:50
• Ah! So the sum is 1*(2^h-1)/(2-1) = 2^h - 1. I still don't understand why it's 2^(h+1) - 1. I checked the starting and ending points. Dec 15, 2017 at 5:53
• Note that $2^h$ is the $(n+1)$th term. So, you have to use the geometric series summing n+1 terms. So, $2^h-1 + 2^h = 2(2^h) -1 =2^{h+1}-1$!
– user371838
Dec 15, 2017 at 5:56
• Yes, thank you! Dec 15, 2017 at 5:57

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