Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$

Question

Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where $$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$

The base case for $n=1$ seems to work, but I am unable to do the induction step.

Answer 1

W.l.o.g. suppose $n = 3^k$: The expand the second part of the function:

$$ T(n) = 9 T(\frac{n}{3}) + n^2 = 9 (9T(\frac{n}{3^2}) + (\frac{n}{3})^2) + n^2 = 9^2 T(\frac{n}{3^2}) +‌ 9(\frac{n}{3})^2 + n^2 = $$ $$ 9^3 T(\frac{n}{3^3}) +‌ 9^2 (\frac{n}{3^2})^2 + 9(\frac{n}{3})^2 + n^2 $$

You can continue it by induction to obtain the following:

$$ T(n) = 9^k T(\frac{n}{3^k}) + 9^{k-1}(\frac{n}{3^{k-1}})^2 + \cdots + 9(\frac{n}{3})^2 + n^2 $$

As $n = 3^k$, $T(\frac{n}{3^k}) = T(1) = 1$. Hence,

$$ T(n) = \sum_{i=0}^k9^i(\frac{n}{3^i})^2 = \sum_{i=0}^k9^i\frac{n^2}{9^i} = \sum_{i=0}^kn^2 = n^2 \times k $$

We know that $k = \log_3(n)$. Therefore:

$$ T(n) = n^2 \log_3(n). $$ and we can say $T(n) = \Theta(n^2 \log(n))$ asymptotically.

Answer 2

Let $n = 3^{k}$ to obtain $T(3^{k}) = 9T(3^{k-1}) + 9^{k}$. This can be written $t_{k} - 9t_{k-1} = 9^{k}$. The characteristic equation is $(x-9)^{2} = 0$. Hence $t_{k} = c_{1}9^{k} + c_{2}k9^{k}$. Putting $n$ back instead of $k$, we find $T(n) = c_{1}n^{2} + c_{2}n^{2}\log_{3}n$. $T(n)$ is therefore $\Theta(n^{2}\log_{3}n)$.