$T(n) = 3T(n/2) + n$ — why does this series not diverge

Question

I'm trying to use a recursion tree to solve the recurrence $T(n) = 3T(n/2) + n$. After drawing out the tree, I can simplify the time formula to
$$
T(n) = n(1 + \frac{3}{2} + \frac{3^2}{2^2} + \dots + \frac{3^{\log_2 n}}{2^{\log_2 n}})
$$
Now here's where I'm confused: why doesn't this series diverge? The common ratio, r, between the terms is $\frac{3}{2}$, which is greater than 1, so shouldn't this series diverge? I know by using Master's Theorem that the time complexity for this algorithm is $\Theta(n^{\log_2 3})$. How do we get to this conclusion from the time formula above?

Answer 1

It does diverge. In fact $$ 1 + \frac{3}{2} + \frac{3^2}{2^2} + \dots + \frac{3^{\log_2 n}}{2^{\log_2 n}} = \frac{3^{\log_2 2n}}{n}-2 $$ which diverges.

How to get the desired form : $$ \begin{aligned} n\left (\frac{3^{\log_2 2n}}{n}-2\right ) &= 3^{\log_2 2n} - 2n \\ &= 3^{\log_2 3 \log_3 2n}-2n\\ &= (2n)^{\log_2 3}-2n \\ &= \Theta(n ^{\log_2 3}) \end{aligned} $$