Simplifying $(3/2)^i$ for $i = 0$ to $\\(log_2 n) -1$

54 Views Asked by At

$$\sum_{i=0}^{\\(log_2 n)-1} \frac{3^i}{2^i}$$

I have been working on solving a recurrence, and finally simplified to this step. However, I am lost as to where to proceed now. I know the sum of powers of 2, but I don't know what to do since it's in the denominator.

2

There are 2 best solutions below

0
On

Hint $$\sum_{i=0}^{N}r^i=\frac{1-r^{N+1}}{1-r}$$ when $r\ne 1$

0
On

$$\sum_{i=0}^{\log_2 n} \frac{3^i}{2^i}=\sum_{i=0}^{\log_2 n} \left(\frac{3}{2}\right)^i.$$

Now use the formula for the sum of a geometric series.