Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method? 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 &gt; 0: \forall n &gt; 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 &gt; 0: \forall n &gt; 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 &gt; 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}) &amp;\Leftrightarrow T(\frac{n}{2}) \leq c_2 (\frac{n}{2})^3\log(\frac{n}{2}) \\
  &amp;\Leftrightarrow 8T(\frac{n}{2}) + n^3 \leq 8c_2 (\frac{n}{2})^3 \log(\frac{n}{2}) + n^3 \\
  &amp; \Leftrightarrow T(n) \leq 8c_2\frac{n^3}{8}(\log(n) - log(2)) + n^3 \\
  &amp; \Leftrightarrow T(n) \leq c_2n^3\log(n) + n^3 - c_2n^3log(2) \\
  &amp; \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 &gt; 0: \forall n &gt; 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?
You can prove precise equality for your recurrence. I'm going to assume the base case:

$$T(n) = \begin{cases}
  8 &amp; n = 2\\
  8T\left(\tfrac{n}{2}\right) + n^3 &amp; n &gt; 2\\
\end{cases}$$

Claim: $T(n) = n^3 \log_2 n$

Base Case ($n = 2$): $T(2) = 8 = 2^3 \log_2 2 = 8$

Inductive Case ($n &gt; 2$):

$$\begin{align*}
T(n) &amp; = 8T\left(\tfrac{n}{2}\right) + n^3\\
     &amp; = 8\left(\tfrac{n^3}{8} \log_2 \tfrac{n}{2}\right) + n^3\\
     &amp; = n^3 \log_2 \tfrac{n}{2} + n^3\\
     &amp; = n^3 \log_2 n - n^3 \log_2 2 + n^3\\
     &amp; = n^3 \log_2 n - n^3 + n^3\\
     &amp; = n^3 \log_2 n &amp; \square
\end{align*}$$

Thus $T(n) = n^3 \log_2 n \implies T(n) = O(n^3 \log n)$. No need to mess with lower or upper bounds. 



However, in general this equality might not be the correct solution. Sometimes you will need to add lower order terms to get the equality or inequality to hold. A general approach to determine the lower order terms is as follows:

If we have:

$$T(n) = \begin{cases}
f(b) &amp; n = b\\
aT(n/b) + f(n) &amp; n &gt; b
\end{cases}$$ 

We first assume $n = b^k$ for some $k$. Next we can turn this into a summation:

$$\begin{align*}
T(n) &amp; = aT(n/b) + f(n)\\
     &amp; = a(aT(n/b^2) + f(n/b)) + f(n)\\
     &amp; = a^2T(n/b^2) + af(n/b) + f(n)\\
     &amp; \vdots\\
     &amp; = \sum_{i = 0}^{\log_b n - 1} a^{i} f\left( \frac{n}{b^i}\right)
\end{align*}$$

Then if you can find a closed form for this sum, we can easily prove equality by induction (e.g. substitution method) with proper constants. Here is your example again:

$$\begin{align*}
T(n) &amp; = 8T\left(\tfrac{n}{2}\right) + n^3\\
     &amp; = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \left( \frac{n}{2^i}\right)^3\\
     &amp; = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \frac{n^3}{2^{3i}}\\
     &amp; = \sum_{i = 0}^{\log_2 n - 1} n^3\\
     &amp; = n^3 \log_2 n\\
\end{align*}$$

Now you can go ahead and use this in your substitution method and you should not have any issues.



Feel free to try the same method with a trickier example:

$$T(n) = \begin{cases}
  12 &amp; n = 3\\
  5T\left(\tfrac{n}{3}\right) + n^2 + n &amp; n &gt; 3\\
\end{cases}$$