Help solving summation series of a recursive function Yesterday in class, we were analyzing the Karatsuba multiplication algorithm and how it applies to recurrence equations.  Time ran short, and I feel I missed how to solve the final summation.
First, we defined the recurrence equation as
$$T(n) = 3T \left(\frac{n}{2}\right) + 4n$$
and applied a recurrence tree such like
$$T(n) = 3T \left(\frac{n}{2}\right) + 4n \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^0$$
$$T\left(\frac{n}{2}\right) = 3T \left (\frac{n}{4} \right) + 4\left(\frac{n}{2}\right) \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^1$$
$$T\left(\frac{n}{4}\right) = 3T \left (\frac{n}{8} \right) + 4\left(\frac{n}{4}\right) \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^2$$
$$T\left(\frac{n}{8}\right) = 3T \left (\frac{n}{16} \right) + 4\left(\frac{n}{8}\right) \Rightarrow 4n \cdot \left(\frac{3}{2}\right)^3$$
Because the denominiator increases in a logarithmic fashion, we defined the summation as
$$\sum_{x=0}^{log_2n} 4n \cdot \left(\frac{3}{2}\right)^x$$
Time was running short, so several steps were skipped, and the final solution was given as
$$9\cdot 3^{log_2n} = 9n^{log_23} = 9n^{1.58} = O(n^{1.58})$$
based on the properties
$$a^{lg\, b} = b^{lg\, a}\: \text{and}\: log_2 3 \approx 1.58$$
I've tried applying the summation formula
$$\sum_{x=0}^{n}r^x = \frac{r^{n+1}-1}{r-1}$$
with this result, and end up with
$$\sum_{x=0}^{n}r^x = \frac{r^{n+1}-1}{r-1} = \sum_{x=0}^{log_2 n} 4n \cdot \left(\frac{3}{2}\right)^x $$
$$= 4\left(n\cdot \frac{\frac{3}{2}^{lg_2n+1}-1}{\frac{3}{2}-1}\right) = 4\left(n \cdot \frac{\frac{3}{2}^{log_2n+1}-1}{\frac{1}{2}}\right) 
= 2\left(n \cdot \frac{3}{2}^{log_2n+1}+1\right) $$
$$=2n \cdot 3^{log_2n+1} + 2$$
which is very different than the solution given.  Where did I go wrong?

The crucial mistake is that you passed somehow from
$$
(\frac32)^{(\log_2 n) +1}
$$
to
$$
3^{(\log_2 n )+ 1}.
$$
Using the rough formula that
$$
\sum_{x=0}^n r^x = O(r^n) \qquad \qquad\text{if $r>1$},
$$
you should get
$$
O(n (\frac32)^{\log_2 n})=O(n e^{(\ln n) \frac{\ln \frac32}{\ln 2}}) = O(n^{1+\frac{\ln \frac32}{\ln 2}}).
$$
Since
$$
1 + \frac{\ln \frac32}{\ln 2} = \frac{\ln 3}{\ln 2} = \log_2 3 = 1.58496...
$$
this is the same as the result you got in class.
