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

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.

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.

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)$$.