# Any suggestions on using induction to prove this inequality?

I am solving an exercise and can't advance in the following induction:

$$n\log n - n + 1 \leq \log n!.$$

If necessary, i put the complete question.

• Update

Calculate $$\lim_{n\to \infty}\frac{n!e^{n}}{n^{n}}$$ following the steps bellow:

A. Show that: $$\int\limits_{1}^{n}\log x\,\mathrm{d}x = n\log n - n + 1 = A_{n}.$$ B. If $B_{n}$ is the right Riemman sum of the function $\log x$ relative to the partition $\lbrace 1, ..., n\rbrace$ of the interval $[1, n]$, show that: $$A_{n} \leq B_{n} = \sum_{k = 2}^{n}\log k = \log n!.$$

C.

D.

E.

F.

The steps C, D, E and F are not relevant for my doubt.

• Adding more detail would be a good idea; people are more likely to help you here when you present the context of the problem and the attempts you've made or thoughts you've had to solve it. – Robert Howard Feb 13 '18 at 5:23
• @RobertHoward , Sure! – Corrêa Feb 13 '18 at 5:27
• The log function is increasing, so the right Riemann sum is greater than or equal to the integral. So the inequality follows from part (A). No need for induction. – fredgoodman Feb 13 '18 at 5:46
• Yes, of course! Thanks for de help! @fredgoodman – Corrêa Feb 13 '18 at 5:57
• Using just the integral from $n$ to $n+1$, you get an inequality equivalent to $(1 + 1/n)^n \le e$. – fredgoodman Feb 13 '18 at 6:02

Base case $n=1 \implies 1\log1-1+1 \leq \log (1!) \implies 0 \leq 0$

Base case $n=2 \implies 2\log2-2+1 \leq \log (2!) \implies \log 2 \leq 1$

We assume this proposition to be true $$\text {(P) }n\log n - n + 1 \leq \log n!$$ We try to prove that

$$(n+1)\log( n+1) - (n+1)+1 \leq \log ((n+1)!)$$ $$(n+1)\log( n+1) - n \leq \log(n+1)+\log (n!)$$ Substract $\log (n+1)$

$$n\log( n+1) - n \leq \log (n)!$$ $$n(\log n( 1+ \frac 1 n)) - n \leq \log (n!)$$ $$n\log(n)+\log( 1+ \frac 1 n)^n - n \leq \log (n!)$$

Note that $\log( 1+ \frac 1 n)^n\leq \log e=1$ And $$n\log(n)+\log( 1+ \frac 1 n)^n - n \leq n\log(n)+1 - n \leq \log (n!)$$ So P is true for $n=1,2$ and we proved by induction that if P is true for n then it's also true for $n+1$ So we can conclude that P is true for any $n \in \mathbb{N} (n\ne 0)$

Starting from the fundamental $(1+\frac{1}{n})^n \leq e$ for all $n>0$, we get the inequality $$\tag{*} en^n \geq (n+1)^n$$

I'd prefer to work with exponentials over logs, so note that your inequality is equivalent to $$\tag{H} n! \geq e\left(\frac{n}{e}\right)^n$$

For the inductive step, we assume $n! \geq e\left(\frac{n}{e}\right)^n$ and want to show $(n+1)! \geq e\left(\frac{n+1}{e}\right)^{n+1}$.

This follows as below. The first inequality is the inductive hypothesis (H) and the second inequality is our knowledge of a lower bound for $e$ (*)

$$(n+1)! = (n+1) n! \geq (n+1) e\left(\frac{n}{e}\right)^n = \frac{n+1}{e^n} en^n \geq \frac{n+1}{e^n}(n+1)^n = e \left(\frac{n+1}{e} \right)^{n+1}$$

Don't forget to establish the base case!

Hint: \begin{align} &((n+1)\log(n+1)-(n+1)+1)-(n\log(n)-n+1)\\ &=\log(n+1)+n\log\left(1+\frac1n\right)-1\\ \end{align} and $$n\log\left(1+\frac1n\right)=\int_n^{n+1}\frac nx\,\mathrm{d}x\lt1$$

Let $F(n)=-n+1+n\ln n.$

Let $G(n)=\ln (n!).$

If $F(n+1)-F(n)\leq G(n+1)-G(n)$ then $(\;F(n)\leq G(n)\implies F(n+1)\leq G(n+1)\;).$

We have $F(n+1)-F(n)=-1-n \ln n +(n+1)\ln (n+1).$

We have $G(n+1)-G(n)=\ln (n+1).$ $$\text {Hence }\quad F(n+1)-F(n)\leq G(n+1)-G(n)\iff$$ $$\iff -1-n \ln n +(n+1)\ln (n+1)\leq \ln (n+1)\iff$$ $$\iff -n \ln n+(n+1)\ln (n+1)\leq 1\iff$$ $$\iff n\ln (1+\frac {1}{n})\leq 1.\quad (\bullet)$$

For $x>0$ we have $\ln (1+x)=\int_1^{1+x}\frac {1}{y}dy$ $<\int_1^{1+x}1dy=x.$ Therefore for $n>0$ we have $n\ln ((1+\frac {1}{n})<n \cdot \frac {1}{n}=1.$

So $(\bullet)$ does hold for all $n>0.$