# Proving this recurrence is $n \log n$

I need to prove that $$T(n)$$ is $$\mathcal O(n\log n)$$ with the substitution method. $$T(n)\leq 3\log n + n + \frac{6}{n}\sum^{2n/3}_{n/3}T(i).$$

This is my attempt: I assume $$T(n) \leq c n \log n$$ and then \begin{align*} T(n) &\leq 3 \log n + n + \frac{6c}{n}\int^{2n/3}_{n/3}x\log x dx\\ &\leq3 \log n + n + \frac{6c}{n} \left[ \frac{1}{2}x^2 \log x - \frac{x^2}{4}\right]\bigg|^{2n/3}_{n/3}\\ &\leq3\log n +n + \frac{6c}{n}\left( \frac{2n^2}{9}\log (\frac{2n}{3}) - \frac{n^2}{18}\log(\frac{n}{3}) -\frac{n^2}{12}\right). \end{align*} I'm stuck at that point, what else can I do?

\begin{align*} & \leqslant 3\log n + n + \frac{6c}n\left(\frac{2n^2}9\log\left(\frac{2n}3\right)-\frac{n^2}{18}\log\left(\frac{n}3\right)-\frac{n^2}{12}\right)\\ & = 3\log n + n + \frac{6c}n\left(\frac{2n^2}9\log n - \frac{n^2}{18}\log n + \frac{2n^2}9\log 2 - \frac{2n^2}9\log3 + \frac{n^2}{18}\log 3 -\frac{n^2}{12}\right)\\ & = 3\log n + n + \frac{6c}n\left(\frac{n^2}6\log n + \frac{2n^2}9\log 2 - \frac{n^2}{6}\log 3 -\frac{n^2}{12}\right)\\ & = cn\log n + 3\log n + n\left(1 + c\frac{4}3\log 2- c\log 3 - \frac{c}2\right)\\ & \leqslant cn\log n \end{align*} The last inequality holds for $$n$$ and $$c$$ big enough, since $$\frac43\log 2 - \log 3 - \frac12<0$$