# How to solve the recurrence $T(n)=3T(n/2)+n$

The exercise stated that i have to solve the recurrence using the Recursion-Tree Method. I have already finished the base part, which is $\Theta(n^{\lg3})$

But for the recursive part I'm having troubles with this sum: $cn*\sum_{i=0}^{\lg n - 1} (3/2)^i$

After resolving, I got that $T(n)=cn*n^{\lg3} - 2cn$ but this answer doesn't match $\Theta(n^{\lg 3})$ which I got using the Master Method

-
Hint: $\sum_{i=0}^{n}r^i=\frac{r^{n+1}-1}{r-1}$. –  Daryl Sep 23 '12 at 7:34

$$\sum\limits_{i=0}^{\lg n-1}(3/2)^i=\Theta((3/2)^{\lg n})\quad\text{and}\quad (3/2)^{\lg n}=2^{\lg(3/2)\lg n}=n^{\lg(3/2)}=n^{\lg3-1}$$