How to analyze the time complexity $\Theta$ of this recurrence I am trying to understand how to show that
$$T(n) = T(n/2) + T(n/4) + n^2$$
is $\Theta(n^2)$ by using a recursion tree. I tried substitution at first but it got real messy real fast.
This is self-study. Problem is from this pdf, problem 1-12.
 A: Suppose we start by solving the following recurrence:
$$T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + n^2$$
where $T(1) = 1$ and $T(0) = 0.$
Now let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$
be the binary representation of $n.$
We unroll the recursion to obtain an exact formula for $n\ge 1$
$$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
[z^j] \frac{1}{1-z-z^2} 
\left(\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right)^2.$$
We recognize the generating function  of the Fibonacci numbers, so the
formula becomes
$$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} F_{j+1}
\left( \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right)^2.$$
We now compute lower and  upper bounds which are actually attained and
cannot  be improved upon.  For the  lower bound  consider a  one digit
followed by a string of zeroes, to give
$$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
F_{j+1} 4^{\lfloor \log_2 n \rfloor-j}
= 4^{\lfloor \log_2 n \rfloor}
\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
F_{j+1} 4^{-j}.$$
Now since $$\left|\frac{1+\sqrt{5}}{2}\right|<4$$
the sum term converges to a number, we have
$$1 \le 
\sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 4^{-j}
\lt \sum_{j=0}^{\infty} F_{j+1} 4^{-j}
= \frac{16}{11}$$
and we thus get for the asymptotics
$$\frac{16}{11} 4^{\lfloor \log_2 n \rfloor}.$$
For an upper bound consider a string of one digits to get
$$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
F_{j+1} 
\left( \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j}\right)^2
= \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
F_{j+1} (2^{\lfloor \log_2 n \rfloor+1-j} - 1)^2
\\ = 4\times 4^{\lfloor \log_2 n \rfloor}
\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
F_{j+1} 4^{-j}
- 4\times 2^{\lfloor \log_2 n \rfloor}
\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
F_{j+1} 2^{-j}
+ \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
F_{j+1}
\\ = 4\times 4^{\lfloor \log_2 n \rfloor}
\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
F_{j+1} 4^{-j}
- 4\times 2^{\lfloor \log_2 n \rfloor}
\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
F_{j+1} 2^{-j}
+ F_{\lfloor \log_2 n \rfloor + 3} - 1.$$
The  same  constant appears  as  in  the lower  bound  as  well as  an
additional constant. Computing these we get
$$\frac{64}{11} \times 4^{\lfloor \log_2 n \rfloor}
- 16\times 2^{\lfloor \log_2 n \rfloor}
+ F_{\lfloor \log_2 n \rfloor + 3} - 1.$$
Doing the asymptotics of these three  terms we obtain a term in $n^2$,
a  term in  $n$ and  a  term in  $n^{\log_2 \varphi}  \in o(n)$  where
$\varphi$ is the golden ratio.

Joining the  upper and the lower  bound we get for  the asymptotics of
this recurrence that it is
$$T(n)\in\Theta\left(4^{\lfloor \log_2  n \rfloor}\right)
= \Theta\left(2^{2\log_2  n}\right) = \Theta(n^2),$$
which, let it be said, could also have been obtained by inspection.

Remark. The evaluation of the constant is done by noting that
the generating function of
$$F_{j+1} 4^{-j}\quad
\text{is}\quad\frac{1}{1-z/4-z^2/16}$$
which at $z=1$ evaluates to $\frac{1}{1-1/4-1/16} = \frac{16}{11}.$
Similarly we have the generating function of
$$F_{j+1} 2^{-j}\quad
\text{is}\quad\frac{1}{1-z/2-z^2/4}$$
which at $z=1$ evaluates to $\frac{1}{1-1/2-1/4} = 4.$
We have a certain  flexibility as to what power of four  to use in the
constant but this does not affect the asymptotics.

A closely related recurrence that  is somewhat simpler may be found at
this MSE link.
A: First consider the homogeneous equation
$$T(n)=T(\frac n2)+T(\frac n4).$$
Letting $n=2^k$,
$$T(2^k)=T(2^{k-1})+T(2^{k-2)}$$ or $$S(k)=S(k-1)+S(k-2).$$
You should recognize the Fibonacci recurrence, with the asymptotic solution 
$$T(n)=S(k)=O(\phi^k)=O(e^{log(\phi)log(n)/log(2)})=O(n^{0.6942\cdots})$$
Then you try a particular solution of the non-homogenous equation, such as $T(n)=an^2$. Plugging in the given equation,
$$an^2=\frac{an^2}4+\frac{an^2}{16}+n^2$$ and 
$$T(n)=\frac{16}{11}n^2$$ works.
As this solution dominates the other, you can conclude $\Theta(n^2)$.
