# Subtracting lower-order term to prove subtitution method works

Substation method fails to prove that $T(n) = \Theta(n^2)$ for the recursion $T(n)= 4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2$.

I don't understand how to subtract off lower-order term to prove that substation works.
Came up with: $T(n) \leq cn^2 - bn^2$ Assume it holds for $T(n/2) \leq c(n/2)^2 - b(n/2)^2$
$T(n) \leq 4(c(n/2)^2 - b(n/2)^2) + n^2 = cn^2- bn^2 + n^2$
However, you there is no way to solve $cn^2- bn^2 + n^2 \leq cn^2 - bn^2$ for $b$

But I am not sure if I am going in the right direction, though mathematics is very elementary. Thanks !

-

$T(n)=4T(n/2)+n^2=4(4T(n/4)+n^2/4)+n^2=16T(n/4)+2n^2=16(T(n/8)+n^2/16)+2n^2=16T(n/8)+3n^2=\cdots=2^{i+1}T(n/2^i)+in^2$
You can follow it till $2^i\approx n\implies$ Number of terms i= $\lfloor\log_2 n\rfloor\implies T(n)\approx nT(1)+n^2\log_2n$ which is surely not $\Theta(n^2)$ but $\Theta(n^2\log_2n)$
If you can actually prove that there’s a positive constant $c$ such that $T(n)<cn^2$, you’re practically done. It’s obvious from the recurrence that $T(n)\ge n^2$, so you would have $n^2\le T(n)<cn^2$, which says that $T(n)$ is $\Theta(n^2)$. However, I seriously doubt that you can do so.