Show that $\sum_{k=2}^{n-1} k\log k\leq \frac12n^2\log n-\frac18n^2$ by splitting the summation into two parts.

Question

Question

Show that $$\sum_{k=2}^{n-1} k\log k\leq \frac12n^2\log n-\frac18n^2$$ Hint: Split the summation into two parts, one for $k=2,3,\dots,\lceil n/2\rceil-1,$ and one for $k=\lceil n/2\rceil,\dots,n-1.$

Solution

Can someone solve the question using the Hint mentioned in Question?
I tried but couldn't do anything, one difficult summation becomes two difficult one and I can't do.

Answer 1

Given any $m$ with $2<m\leq n-1,$

$$\begin{align}\sum_{k=2}^{n}k\log_2 k&=\sum_{k=2}^{m-1} k\log k+\sum_{k=m}^{n-1} k\log_2 k\\ &\leq\sum_{k=2}^{m-1}k\log_2(m-1)+\sum_{k=m}^{n-1}k\log_2 (n-1)\\ &=\frac{(m+1)(m-2)}{2} \log_2 (m-1)\\&\quad+\frac{(m+n-1)(n-m)}{2}\log_2 (n-1) \end{align}$$

Now you need to know that

$$\log_2(m-1)\leq \log_2(n/2)=\log_2(n)-1.$$

Finally, when $m=\lceil n/2\rceil,$ then show:

$$\frac{(m+1)(m-2)}{2}\leq \frac{n^2}{8}\\ \frac{(n+m-1)(n-m)}2\leq \frac{3n^2}{8}.$$

So I get:

$$\sum_{k=2}^{n-1}k\log_2 k\leq \frac{n^2}{4}\log_2 n-\frac{n^2}8.$$