<s>[INST] 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?
 [/INST] 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).$$
</s>