# Summations help!

• February 15th 2011, 07:15 AM
collegestudent321
Summations help!
Hello,
I am trying to solve a summation but i keep getting the wrong answer:

summation of 2^i from i=0 to i=h/2

I have tried using the geometric series equation and have gotten:(2^((h/2)+1) - 1) / (2-1) which simplifies to 2^((h/2)+1) - 1 but I don't know how to simplify it from there, assuming it is correct. The answer is said to be: 2^(h+1) - 1. Any help would be very much appreciated. Thank you!
• February 15th 2011, 07:35 AM
Plato
Quote:

Originally Posted by collegestudent321
I am trying to solve a summation but i keep getting the wrong answer:
summation of 2^i from i=0 to i=h/2

In what context does the sum occur?
We usually have indices that are integers, $\frac{h}{2}$ may not be an integer.
If this is a counting question, your sum may be like this: $\displaystyle
\sum\limits_{k = 1}^{\left\lfloor {\frac{h}{2}} \right\rfloor } {2^{ k} }$
.
We use the floor function to get an integral index.
• February 15th 2011, 07:41 AM
collegestudent321
Basically, the summation goes like this:

1 + 2 + 2^2 + 2^3 + ... + 2^(h/2)

I do believe h/2 is an integer because h represents the height of a binary search tree. I just can't remember how to work with these summations.

According to the answer, the geometric series equation is used and is as follows: (1 - 2^((2/h)+1)) / (1-2)
• February 15th 2011, 07:54 AM
Plato
Quote:

Originally Posted by collegestudent321
Basically, the summation goes like this: 1 + 2 + 2^2 + 2^3 + ... + 2^(h/2)
h represents the height of a binary search tree. I just can't remember how to work with these summations.

In the future, please give the context of the question.

In general, $\displaystyle\sum\limits_{k = 1}^J {2^k } = 2^{J + 1} - 2$.