For $T(n) = 16(T/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$ 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 &lt; 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
$$

Now,

$$
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?
What you want to prove is false.

$T(n) = 16 T(n/4) + n^2\log^3 n$ has solution $T(n) = \Theta(n^2 \log^4 n)$.

To see this notice that this recurrence fits in the general form $T(n) = a T(n/b) + f(n)$ once you set $a=16, b=4, f(n)=n^2\log^3 n$.

Since $f(n) = n^2 \log^3 n = \Theta( n^{ \log_b a } \cdot \log^k n)$ for $k=3$, you can apply the Master theorem to conclude that $T(n) = \Theta(n^{ \log_b a } \cdot \log^{k+1} n)$.