Define: $ \lg x = \log_2x $.
Let $ f(n), g(n) $ be some non-negative functions.
Define $ f(n) = \Theta (g(n)) $ if $$ \exists c_1,c_2 \in R\colon 0 < c_1g(n) \leq f(n) \leq c_2g(n) $$
I want to prove that the function defined by the recurrence relation $ T(n) = 16(T/4) + n^2\lg^3n $ has the asymptotics $ T(n) = \Theta(n^2\lg^3n) $
I wanted to prove that by substitution method:
$$ T(n/4) \leq n^2\lg^3n $$
$$ T(n) \leq 16(n^2\lg^3n) + n^2\lg^3n = 17n^2\lg^3n $$
But in order for the proof to work, I should have gotten
$$ T(n) \leq n^2\lg^3n $$
I also need to show that this is a lower bound, but I want to start by showing that it's an upper bound.
What is the right way to prove these things?