Solving $T(n)=4T(n/2)+n^2$ I am trying to solve a recurrence by using substitution method. The recurrence relation is:
$$T(n)=4T(n/2)+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)\le cn^2\log n$ but that did not work, I got $T(n)\le cn^2\log n+n^2$.

I then tried to show that, if $T(n)\le c_1 n^2\log n-c_2 n^2$, then it is also $\mathcal O(n^2\log n)$, but that also did not work and I got $T(n)\le c_1n^2\log(n/2)-c_2 n^2+n^2$.

What trick can I use to show that? Thanks.
You must subtract a lower order term in order to strengthen your inductive hypothesis: try

$T(n) \leq c_1 n^2 \lg n- c_2 n$ and you will be able to show by substitution that $T(n) = O(n^2 \lg n)$ for appropriate values of the constants ($c_2 &gt; 1$ and $c_1$ big enough to correctly handle the initial conditions).