I've seen plenty of discussion regarding solving recurrences like this with the master theorem, but I need to solve it via back substitution. Was doing pretty good until I got stuck in the summation part.
Assumptions are that $n$ is a power of $3$ so $n = 3^k$ and hence $k = \log_3(n)$. Also $T(1) = 1$.
After substituting $3$ functions to recognize the pattern I found this general form for the recurrence:
And then I followed with:
However this is the part where I got stuck:
I have absolutely no idea of how to resolve that sum, I tried applying logarithm properties to get a difference instead of division and then make two separated and simplier sums, but I still couldn't find or figure out if I can use any summation identities.
Best Answer
I will redo the work from begginning also using $\lg x=\log_2 x$ as binary logarithm.
First I will iterate the first term, then later combine it with the sum which the second term gave:$$T(n)=3T\left(\frac{n}{3}\right)+n\lg n$$ $$3T\left(\frac{n}{3}\right)=3\left(3T\left(\frac{n}{3^2}\right)+\frac{n}{3}\lg\frac{n}{3}\right)=3^2T\left(\frac{n}{3^2}\right)+n\lg\frac{n}{3}$$ $$3^2T\left(\frac{n}{3^2}\right)=3^2\left(3T\left(\frac{n}{3^3}\right)+\frac{n}{3^2}\lg\frac{n}{3^2}\right)=3^3T\left(\frac{n}{3^3}\right)+n\lg\frac{n}{3^2}$$ $$\dots$$ $$3^{k-1}T\left(\frac{n}{3^{k-1}}\right)=3^kT\left(\frac{n}{3^k}\right)+n\lg\frac{n}{3^{k-1}}$$ The recursion ends when we hit $T(1)$, thus we can take $k$ from there:
$$T\left(\frac{n}{3^k}\right)=T(1)\Rightarrow n=3^k\Rightarrow k=\log_3n$$ $$\Rightarrow T(n)=3^k \cdot \underbrace{T(1)}_{=1}+n\lg n +n\lg\frac{n}{3}+\dots+n\lg\frac{n}{3^{k-1}}$$ $$=\underbrace{3^{\log_3 n}}_{=n} \cdot 1 +\sum_{i=0}^{k-1}n \lg\frac{n}{3^{i}}=n+n\sum_{i=0}^{k-1}\left(\lg n-\lg3^{i}\right),\quad \quad a^{\log_a b}=b^{\log_a a}$$ $$=n+n\lg n \sum_{i=0}^{k-1}1-n\sum_{i=0}^{k-1}i \cdot \lg 3, \quad \quad \lg a^b = b\lg a$$ $$=n+n\lg n \cdot k -n\lg 3 \cdot \frac{(k-1)k}{2}$$ $$=n+n\lg n \cdot \frac{\lg n}{\lg 3}-\frac{\lg 3}{2}n\left(\frac{\lg n}{\lg 3}-1\right)\frac{\lg n}{\lg 3},\quad \quad k=\log_3 n =\frac{\lg n}{\lg 3}$$ $$=n+\frac{1}{\lg 3} n\lg^2 n -\frac12 \frac{1}{\lg 3}n\lg^2 n+\frac12 n\lg n$$ $$\boxed{T(n)=n+\frac1{2\log_2 3} n\log_2^2 n +\frac12 n\log_2 n}$$