sum of $f(x)$ being less than integral

Question

I have to prove that: $$ \quad \sum_{j=1}^{n-1} j \ln(j) \leq \int_{1}^{n} x \ln(x) \ \mathrm{d}x $$ I am wondering whether inductive prove is possible, I evaluated integral and got closed formula and then started induction on $n$, however inductive step seems hard to prove for me.

$$ \text{Inductive Hypothesis:} \quad \sum_{j=1}^{k-1} j \ln(j) \leq \int_{1}^{k} x \ln(x) \ \mathrm{d}x $$

Answer 1

Alternatively notice that

$$\frac{\mathrm{d}}{\mathrm{d}x}\bigl(x\ln x\bigr)=\ln x+1>0$$

for all $x>\frac{1}{e}$, meaning that $x\mapsto x\ln x$ is strictly increasing on $\left(\frac{1}{e},\infty\right)$, so

\begin{align*} \int_1^nx\ln x\,\mathrm{d}x &=\sum_{j=1}^{n-1}\int_j^{j+1}x\ln x\,\mathrm{d}x \\ &\geq\sum_{j=1}^{n-1}\int_j^{j+1}j\ln j\,\mathrm{d}x \\ &=\sum_{j=1}^{n-1}j\ln j. \end{align*}

---

We can use the same idea to do an inductive proof. The base case $n=1$ is trivial, as both sides are $0$. Suppose now that the inequality holds for some $n\in\mathbb{Z}^+$. Then, since $x\mapsto x\ln x$ is increasing on $[n,n+1]$,

\begin{align*} \int_1^{n+1}x\ln x\,\mathrm{d}x &=\int_1^nx\ln x\,\mathrm{d}x+\int_n^{n+1}x\ln x\,\mathrm{d}x \\ &\geq\sum_{j=1}^{n-1}j\ln j+\int_n^{n+1}x\ln x\,\mathrm{d}x \\ &\geq\sum_{j=1}^{n-1}j\ln j+\int_n^{n+1}n\ln n\,\mathrm{d}x \\ &=\sum_{j=1}^{n-1}j\ln j+n\ln n \\ &=\sum_{j=1}^nj\ln j, \end{align*}

from which the result follows.

Answer 2

Note that $f(x) =x\ln(x)$ satisfies $f'(x) =\ln(x)+1 \gt 0 $ for $x > 1/e$.

More generally, if $f'(x) > 0$ then $f(x) \lt \int_x^{x+1} f(t) dt $ because

$\begin{array}\\ \int_x^{x+1} f(t) dt-f(x) &=\int_x^{x+1} (f(t)-f(x) dt\\ &\gt 0\\ \end{array} $

since $f(t)>f(x)$ for $x < t \le x+1$.

Therefore

$\begin{array}\\ \sum_{j=1}^{n-1} f(j) &\lt \sum_{j=1}^{n-1} \int_j^{j+1} f(t)dt\\ &=\int_1^n f(t) dt\\ \end{array} $

This can be converted to an inductive proof by using the base case $(n=2)$ $\sum_{j=1}^{n-1} f(j) \lt \int_1^n f(t) dt $ and $f(n) \lt \int_n^{n+1} f(t) dt $.

Also note that $f(x+1) \gt \int_x^{x+1} f(t) dt $ so that $\sum_{j=1}^{n-1} f(j+1) \gt \int_1^n f(t) dt $.

The inequalities are reversed if $f'(x) < 0$.