How to simplify the summation of a recurrence relation After solving the recurrence relation
$$T(n) = 3T(\frac{n}{3}) + n\log(n)$$
I get following equation
$$T(n)=3kT(\frac{n}{3k})+ n\log(n) + n\log(\frac{n}{3}) + n\log(\frac{n}{3^2})+\dots+n\log(\frac{n}{3^k})$$
I don't know how to simplify the summation and how to know the asymptotic function?
 A: Let $n=3^k$. We have,
$T(n)=3^kT(\frac{n}{3^k})+ n\log(n) + n\log(\frac{n}{3}) + n\log(\frac{n}{3^2})+\dots+n\log(\frac{n}{3^k})$
$=3^k.T(1)+n\log\left(n.\frac{n}{3^1}.\frac{n}{3^2}\ldots.\frac{n}{3^k}\right)$
$=3^k.1+n\log\left(n.\frac{n^k}{3^{1+2+\ldots+k}}\right)$ (since $T(1)=1$)
$=3^k+n\log\left(\frac{n^{k+1}}{3^{1+2+\ldots+k}}\right)$
$=3^k+n\log\left(\frac{(3^k)^{k+1}}{3^{k(k+1)/2}}\right)$
$=3^k+n\log\left(\frac{3^{k(k+1)}}{3^{k(k+1)/2}}\right)$
$=3^k+3^k\log\left(3^{k(k+1)/2}\right)$
$=3^k+3^k.k(k+1)/2.\log3$
$=3^k+\Theta(3^k.k^2)$
$=\Theta(3^k.k^2)$
$=\Theta(n.(\log n)^2)$ (since $n=3^k$)
Or use Master theorem:
$T(n) = 3T(\frac{n}{3}) + n\log(n)$, here $c_{crit}=\log_b a = \log_3 3 = 1$, $k=1$, hence, we have,
$T(n) = \Theta(n^{c_{crit}}\log^{k+1}n)=\Theta(n\log^2 n)$
A: Assuming $\log n = \ln n$ we have
$$
T\left(3^{\log_3 n}\right)=3T\left(3^{\log_3 \left(\frac n3\right)}\right)+n\frac{\log_3 n}{\log_3 e}
$$
now calling $\mathcal{T}(\cdot)=T\left(3^{(\cdot)}\right)$ and $z = \log_3 n$ we follow with the recurrence
$$
\mathcal{T}(z)= 3 \mathcal{T}(z-1)+z3^z c_0
$$
with solution
$$
\mathcal{T}(z)= 3^{z-1}c_1+z(z+1)3^z\frac{c_0}{2}
$$
and now going backwards with $z = \log_3 n$ we arrive at
$$
T(n) = \frac n3 c_1 +n(\log_3 n) (1+\log_3 n)\frac {c_0}{2}
$$
NOTE
The recurrence $\mathcal{T}(z)= 3 \mathcal{T}(z-1)+z3^z c_0 $ is linear so the solution can be composed as $\mathcal{T}(z)=\mathcal{T}_h(z)+\mathcal{T}_p(z)$. The homogeneous solution is direct
$$
\mathcal{T}_h(z) = 3^{z-1}c_1
$$
now taking as particular $\mathcal{T}_p(z) = 3^{z-1}c_1(z)$ and substituting into the complete recurrence we get
$$
c_1(z) = c_1(z-1)+3z c_0
$$
hence
$$
c_1(z) = \frac 32z(z+1)c_0
$$
etc.
