Can someone prove this inequality?

Question

I am trying to prove the following inequality, but I cannot.

Can someone help me?

I'll appreciate any small hints.

$$ \sum_{k=2}^{n-1}k\log_2k \le \frac12 n^2 \log_2n - \frac18 n^2 $$

Answer 1

hint:

Follow the professor's hint and the above comment: $\displaystyle \sum_{k=2}^{n-1} k\log_2k\leq \displaystyle \int_{2}^n x\log_2xdx$. The right side should come out from this.

Answer 2

Try bounding the sum by an integral. Note that $k \log_2 k$ is an increasing function on $[2,\infty)$

Answer 3

I am really appreciate many hints and advice. Thanks to them, I could success proving this proposition state.

---

Prove that $$ \sum_{k=2}^{n-1}k\log_2k \le \frac12n^2 \log_2n-\frac18n^2 $$

---

Proof: \begin{align*} \sum_{k=2}^{n-1} k \log_{2}{k} &\le \int_{2}^{n} x \log_{2}{x} {dx}\\ &=\left[\frac{x^2}{2}{\log_2x}\right]_{2}^{n} - \int_{2}^{n} \frac{x^2}{2}\frac{1}{x\ln2}dx\\ &=\left[\frac{x^2}{2}{\log_2x}\right]_{2}^{n} - \int_{2}^{n} \frac{x}{2\ln2}dx\\ &=\left[\frac{x^2}{2}{\log_2x}\right]_{2}^{n} - \left[\frac{x^2}{4\ln2}\right]_{2}^{n}\\ &=\left[\frac{x^2}{2}{\log_2x} - \frac{x^2}{4\ln2}\right]_{2}^{n}\\ &=\left[\frac{n^2}{2}{\log_2n} - \frac{n^2}{4\ln2}\right] - \left[2 - \frac{1}{\ln2}\right]\\ &=\frac{1}{2}{n^2}{\log_2n} - \frac{n^2}{4\ln2} - 2 + \frac{1}{\ln2}\\ &=\frac{1}{2}{n^2}{\log_2n} - \frac{1}{8}n^2\left(\frac{2}{\ln2}+\frac{16}{n^2}-\frac{8}{n^2\ln2}\right) \end{align*}

---

\begin{align*} \frac{2}{\ln2}+\frac{16}{n^2}-\frac{8}{n^2\ln2} &\ge 1\\ \frac{2n^2+16\ln2-8}{n^2\ln2} &\ge 1\\ 2n^2+16\ln2-8 &\ge n^2\ln2\\ (2-\ln2)n^2 &\ge 8(1-2\ln2) = 8\left(\ln\frac{e}{4}\right)\\\\\\ \therefore \frac{2}{\ln2}+\frac{16}{n^2}-\frac{8}{n^2\ln2} &\ge 1\\ \big(\because (2-\ln2)n^2 &\gt 0 , \ \ \ 8\left(\ln\frac{e}{4}\right) \lt 0\big) \end{align*}

---

\begin{align*} \sum_{k=2}^{n-1}k\log_2k &\le \int_{2}^{n} x \log_{2}{x} {dx}\\ &= \frac{1}{2}{n^2}{\log_2n} - \frac{1}{8}n^2\left(\frac{2}{\ln2}+\frac{16}{n^2}-\frac{8}{n^2\ln2}\right)\\ &\le \frac12n^2 \log_2n-\frac18n^2 \end{align*}

Answer 4

Summation by parts gives:

$$ \sum_{k=1}^{n}k\log_2 k = \frac{n(n+1)}{2}\log_2(n) - \sum_{k=1}^{n-1}\frac{k(k+1)}{2}\left(\log_2(k+1)-\log_2(k)\right) $$ but since $\log_2(1+x)$ is a concave function on $[0,1]$, we have: $$ \sum_{k=1}^{n}k\log_2 k \leq \frac{n(n+1)}{2}\log_2(n)-\sum_{k=1}^{n-1}\frac{k+1}{2} $$ hence:

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