# Big theta notation in substitution proofs for recurrences

Often in CLRS, when proving recurrences via substitution, $$\Theta(f(n))$$ is replaced with $$cf(n)$$.

For example, on page 91, the recurrence

$$T(n) = 3T(⌊n/4⌋) + \Theta(n^2)$$

is written like so in the proof

$$T(n) \le 3T(⌊n/4⌋) + cn^2.$$

But can't $$\Theta(n^2)$$ stand for, let's say, $$cn^2 + n$$? Would that not make such a proof invalid?

Further in the proof, the statement

\begin{align} T(n) &\le (3/16)dn^2 + cn^2 \\ &\le dn^2 \end{align}

is reached. But if $$cn^2 + n$$ was used instead of $$cn^2$$, that step would instead be the following

$$T(n) \le (3/16)dn^2 + cn^2 + n$$

Can it still be proven that $$T(n) \le dn^2$$ if this is so? Do such lower order terms not matter in proving recurrences via substitution?

By definition, a function $$f(n)$$ is $$\Theta(n^2)$$ if there exist constant $$b,c,N$$ such that for all $$n \geq N$$, $$bn^2 \leq f(n) \leq cn^2.$$ In particular, as long as $$n \geq N$$, we can always replace $$f(n)$$ by $$cn^2$$ when upper-bounding an expression.
In your example of $$cn^2 + n$$, when $$n \geq 1$$ we have $$n \leq n^2$$ and so $$cn^2 \leq (c+1)n^2$$.
Let me also suggest the following vision of the situation: $$\Theta(f)$$ is set of functions, which satisfy well know definition. So, when you wrote $$T(n) = 3T(⌊n/4⌋) + \Theta(n^2)$$, then this means $$T(n) \in 3T(⌊n/4⌋) + \Theta(n^2)$$, where right side is again set $$g+\Theta(f) = \{g+\phi \colon \phi \in \Theta(f) \}$$.
So, $$T \in g+\Theta(f)$$ mean that exists element of $$g+\Theta(f)$$ which is equal to $$T$$, but we cannot say, that $$T$$ equals to any member of $$g+\Theta(f)$$.
Same is if we write $$T(n)- 3T(⌊n/4⌋) \in \Theta(n^2)$$ Now, knowing the definition of belonging to a set, we just use it and write, that $$\exists c_1, c_2 \gt 0, N\in \mathbb{N}$$, such that for $$n \gt N$$ $$c_1 n^2 \leqslant T(n)- 3T(⌊n/4⌋) \leqslant c_1 n^2$$ saying exactly we do not "replace" $$T(n)- 3T(⌊n/4⌋)$$ in equality, but we "estimate" it in inequality.