Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$
with base case $T(n) = 1$ if $n \leq 1$.
I know that the solution is(with the help of the Master Theorem) $$\Theta(n*log^2(n))$$
I tried without the Master theorem and witht the help of the substuition method I got the following expression
$$T(n)=n+2*n*\sum_{k=0}^{log_{3}(n)-1}log(\frac{n}{3^k})$$
How can I convert this expression into a valid $\Theta(n*log^2(n))$ expression ?
Let's suppose $n=3^k$. Then we have:
$$T(n)=3^kT(1)+2n\log \frac{n^k}{3^{k-1}\cdots3^0}=n+2n\log 3^{k^2-\frac{k(k-1)}{2}} =\\
=n+2n\log n \cdot \frac{\log_3 n+1}{2}   $$
Hope it helps.