To make my question more concrete, here is an example I am stuck on.
I want to prove that $T(n) = 8T(\frac{n}{2}) + n^3$ is asymptotic bound by $n^3\log(n)$ using the substution method. That is $T(n)$ is $\Theta(n^3\log(n))$, so both $O(n^3\log(n))$ and $\Omega(n^3 \log(n))$.
We know $T(n) = \Theta(n^3 \log(n)) \Leftrightarrow \exists c_1, c_2, n_0 > 0: \forall n > n_0 . c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$.
Given that I assume the proof should go somewhat as follows:
To show: $\exists c_1, c_2, n_0 > 0: \forall n > n_0 . c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$
To do this we can use strong induction.
Let $P(n)$ be $c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$.
Take $n$ to be an arbitrary natural number.
Induction hypothesis: $P(1),P(2),...,P(n-1)$. And notably, $P(\frac{n}{2})$.
It seems fairly straight forward to show the right-hand side of $P(n)$, that is that $\forall n > n_0 . T(n) \leq c_2 n^3 \log(n)$.
It follows that (taking $\log$ to be in base $2$):
$$ \begin{align*} P(\frac{n}{2}) &\Leftrightarrow T(\frac{n}{2}) \leq c_2 (\frac{n}{2})^3\log(\frac{n}{2}) \\ &\Leftrightarrow 8T(\frac{n}{2}) + n^3 \leq 8c_2 (\frac{n}{2})^3 \log(\frac{n}{2}) + n^3 \\ & \Leftrightarrow T(n) \leq 8c_2\frac{n^3}{8}(\log(n) - log(2)) + n^3 \\ & \Leftrightarrow T(n) \leq c_2n^3\log(n) + n^3 - c_2n^3log(2) \\ & \Leftrightarrow T(n) \leq c_2n^3\log(n) + n^3 - c_2n^3 \leq c_2n^3\log(n) \ \text{ (if $c_2 \geq 1$)} \end{align*} $$
So we have $P(n)$.
And as such $\exists c_2, n_0 > 0: \forall n > n_0 . T(n) \leq c_2 n^3 \log(n)$.
My problem:
So we have shown that $T(n) = O(n^3 \log (n))$ but not yet that $T(n) = \Omega(n^3 \log (n))$ which is also required to have $T(n) = \Theta(n^3 \log(n))$.
And that is what I am not sure how to go about showing — the left-hand side of $P(n)$, that is that given $P(\frac{n}{2})$, we have $c_2 n^3 \log(n) \leq T(n)$.
Can someone provide some insight into how to approach this?