Any suggestions on using induction to prove this inequality?

Question

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_{1}^{n}\log x\,\mathrm{d}x = n\log n - n + 1 = A_{n}.$$ B. If $B_{n}$ is the right Riemann sum of the function $\log x$ relative to the partition $\lbrace 1, \ldots, 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.

Answer 1

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)$

Answer 2

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!

Answer 3

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.$

Answer 4

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 $$