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?
 A: 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.
A: This recurrence has the nice property that we can compute explicit values for $T(n)$ the same way as was done here, for example. 
Let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary digit representation of $n.$ It is not difficult to see that with $T(0)=0$ we have $$ T(n) = 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} 3^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j} = 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
\left( \frac{3}{2} \right)^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
Now for an upper bound consider $n$ consisting only of one digits, giving
$$ T(n) \le 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
\left( \frac{3}{2} \right)^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k =
4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left( \frac{3}{2} \right)^j 
\left( 2^{\lfloor \log_2 n \rfloor + 1} - 2^j\right) $$
which is $$ 4 \left( 2^{\lfloor \log_2 n \rfloor + 1} \frac{(3/2)^{\lfloor \log_2 n \rfloor + 1}-1}{3/2-1} - \sum_{j=0}^{\lfloor \log_2 n \rfloor}3^j \right) =
4 \left(2 \left( 3^{\lfloor \log_2 n \rfloor + 1} - 2^{\lfloor \log_2 n \rfloor + 1}\right) 
- \frac{3^{\lfloor \log_2 n \rfloor + 1}-1}{3-1} \right)
= 2\times 3^{\lfloor \log_2 n \rfloor + 2} - 2^{\lfloor \log_2 n \rfloor + 4} + 2.$$
For a lower bound, take all digits zero except the leading one, getting
$$ T(n) \ge 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
\left( \frac{3}{2} \right)^j 2^{\lfloor \log_2 n \rfloor} =
2^{\lfloor \log_2 n \rfloor + 2} \frac{(3/2)^{\lfloor \log_2 n \rfloor + 1}-1}{3/2-1} =
4\times 3^{\lfloor \log_2 n \rfloor + 1} - 2^{\lfloor \log_2 n \rfloor + 3} .$$
The lower bound and the upper bound taken together show that
$$ T(n) \in \Theta\left(3^{\lfloor \log_2 n \rfloor}\right) =
\Theta\left(2^{\log_2 3 \lfloor \log_2 n \rfloor} \right) =
\Theta\left(n^{\log_2 3}\right).$$
