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 gotten2^((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!
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)