In this lecture of an introductory class to algorithms (video here, time 74:09), the professor cites the following as an upper bound:
$ \sum_{k=2}^n k \lg k \leq \frac{1}{2} n^2 \lg n - \frac{1}{8} n^2.$
The professor cites two ways of seeing the inequality: 1) by "using purely summations and facts about summations by splitting the summation into two pieces and reconstituting it", and 2) by using an integral.
The integral method can be solved by integration by parts:
$ \sum_{k=2}^n k \lg k \leq \int_{2}^n x \lg x = \frac{1}{2} x^2 \lg x - \frac{1}{4\ln 2} x^2 < \frac{1}{2} n^2 \lg n - \frac{1}{8} n^2.$
I tried doing it by sums, but am not sure what to split. One can find: $\begin{align} \sum_{k=2}^n k \lg k &= 2 \lg 2 + 3 \lg 3 + \cdots + (n-1)\lg(n-1) \\ &\leq 2\lg(n-1) + 3\lg(n-1) + \cdots (n-1) \lg(n-1) \\ &\leq \lg(n-1) \sum_{k=2}^n k = \lg(n-1) \frac{n^2-n-2}{2}, \end{align}$ which satisfies the first term in the upper bound. But how does one get the square term $(-n^2/8)$ by sums?