Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method I am trying to solve a recurrence by using substitution method. The recurrence relation is:
$$T(n)=4T\left(\frac{n}{2}\right)+n^2$$
My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it because of master theorem), and to find an upper bound, I use induction. I tried to show that $T(n)\leq cn^{2}\log n$ but that did not work, I got $T(n)\leq cn^{2}\log n+n^{2}$. Then I tried to show that, if $T(n)\leq c_{1}n^{2}\log n-c_{2}n^{2}$, then it is also $O(n^{2}\log n)$, but that also did not work and I got $T(n)\leq c_{1}n^{2}\log(n/2)-c_{2}n^{2}+n^{2}$. What trick can I do to show that? Thanks
 A: If $T(\frac{n}{2}) \leq c(\frac{n}{2})^2\log_2(\frac{n}{2})+T(1)$, then 
\begin{align}
T(n)=4T\left(\frac{n}{2}\right)+n^2 & \leq 4c\left(\frac{n}{2}\right)^2\log_2\left(\frac{n}{2}\right)+4T(1)+n^2 \\ 
&=cn^2\log_2(n)-cn^2+4T(1)+n^2 \\
&\leq cn^2\log_2(n)+T(1)
\end{align}
for $c \geq 1+3T(1)$.
A: By way of enrichment we  solve another closely related recurrence that
admits an exact  solution.  Suppose we have $T(0)=0$  and for $n\ge 1$
(this gives $T(1)=1$) 
$$T(n) = 4 T(\lfloor n/2 \rfloor) + n^2.$$
Furthermore let the base two representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
Then we  can unroll the  recurrence to obtain the  following exact
formula for $n\ge 1$
$$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
4^j \left(
\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}
\right)^2
= \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
\left(\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k\right)^2.$$
Now to get an upper bound consider a string of one digits which yields
$$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
\left(\sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k\right)^2.$$
Note that this bound is attained and cannot be improved. It simplifies
to
$$\left(4 \lfloor \log_2 n \rfloor - \frac{8}{3}\right)
\times 4^{\lfloor \log_2 n \rfloor}
+ 4 \times 2^{\lfloor \log_2 n \rfloor}
- \frac{1}{3}.$$
The lower bound is for the case of a one digit followed by a string of
zeros and yields
$$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
2^{2\lfloor \log_2 n \rfloor}.$$
It simplifies to
$$(1+\lfloor \log_2 n \rfloor)
2^{2\lfloor \log_2 n \rfloor}.$$

Joining the dominant terms of the upper and the lower bound we obtain
the asymptotics
$$\color{#006}{\lfloor \log_2 n \rfloor 2^{2 \lfloor \log_2 n \rfloor}
\in \Theta\left(\log_2 n \times  2^{2 \log_2 n}\right) 
= \Theta\left(\log n \times n^2\right)}.$$
These are both in agreement with what the Master theorem would produce.
This MSE link has a series of similar calculations.
