First Order Recursion Well I got this problem: 
$$T(0) = 0$$
$$T(n) = 3T(n/2) + n, n \geq 1$$
I simplified the equation to the following.
$$3^iT(n/2^i) + 2n((3/2)^i - 1)$$
From this point I am confused how to solve. 
Thanks for any help.
 A: Since $n$ is integer, what is $T(n)$ when $n == 1$?
Other than that, let $n = 2^m$ we have,
$$
T(2^m) = 3T(2^{m-1}) + 2^m, m \ge 0
$$
Let $f(m) = T(2^m)$, 
$$
f(m) = 3f(m-1) + 2^m
$$
=>
$$
f(m) + 2^{m+1}  = 3(f(m-1) + 2^m)
$$
If you can solve
$$g(m) = f(m) + 2^{m+1} = 3g(m)$$ 
you will got the idea.
It looks like a high school math question though. 
A: I claim that $\boxed{T(n) = \Theta(n^{\log_2 3})}$. This magical claim came from Case 1 of the Master Method. To see this, I will prove it by induction (I'll skip the base case).
Induction Hypothesis: Assume that there exist some $a,b,c,d>0$ such that for all $k<n$, we have:
$$
ak^{\log_2 3} + bk \leq T(k) \leq ck^{\log_2 3} - dk
$$
It remains to prove that the inequality holds true for $k=n$. Observe that:
\begin{array}{rcccl}
3T(n/2) + n &=& T(n) &=& 3T(n/2) + n \\
3\left[a\left(\dfrac{n}{2}\right)^{\log_2 3} + b\left(\dfrac{n}{2}\right)\right] + n &\leq& T(n) &\leq& 3\left[c\left(\dfrac{n}{2}\right)^{\log_2 3} - d\left(\dfrac{n}{2}\right) \right] + n\\
3\left[a\left(\dfrac{n^{\log_2 3}}{3}\right) + \left(\dfrac{b}{2}\right)n\right] + n &\leq& T(n) &\leq& 3\left[c\left(\dfrac{n^{\log_2 3}}{3}\right) - \left(\dfrac{d}{2}\right)n \right] + n\\
\left[an^{\log_2 3} + \left(\dfrac{3b}{2}\right)n\right] + n &\leq& T(n) &\leq& \left[cn^{\log_2 3} - \left(\dfrac{3d}{2}\right)n \right] + n\\
\left[an^{\log_2 3} + bn\right] + \left(\dfrac{b}{2} + 1 \right)n &\leq& T(n) &\leq& \left[cn^{\log_2 3} - dn \right] + \left(1-\dfrac{d}{2}\right)n\\
an^{\log_2 3} + bn &\leq& T(n) &\leq& cn^{\log_2 3} - dn\\
\end{array}
provided that $d \geq 2$. This completes the induction.
