Cannot follow proof that $n! \leq en(n/e)^n$

Question

prove that

$n! \leq en(n/e)^n$

skip proof for base ($n=1$)...

Assume it holds for $n-1$, verify for $n$. We have

$n! = n\cdot (n-1)! \leq n \cdot e(n-1)\big(\frac{n-1}{e}\big)^{n-1} $ by inductive assumption.

we transform the right hand side to

$e\,n\big(\frac{n}{e}\big)^{n} \big(\frac{n-1}{n}\big)^n e$

How is the last step transformed?

subquestion: What can I do to improve my algebraic manipulation skills? Unfortunately most of the proofs that use induction assume that people can follow these transformations and just skip describing them verbosely.

Answer 1

The base case trivial, so assume it holds for $n-1$, i.e. $(n-1)!\le e(n-1)\left(\frac{n-1}e\right)^{\!n-1}$. Then \begin{align*}n!&=n\cdot(n-1)!\le n\cdot e(n-1)\left(\frac{n-1}e\right)^{\!n-1}=ne\cdot(n-1)\frac{(n-1)^{n-1}}{e^{n-1}}\\&=ne\cdot\frac{(n-1)^n}{e^{n-1}}=ne\cdot\frac{(n-1)^n}{e^n}\cdot e=ne\cdot\frac{(n-1)^n\cdot n^n}{e^n\cdot n^n}\cdot e\\&=ne\cdot\frac{n^n}{e^n}\cdot\frac{(n-1)^n}{n^n}\cdot e=ne\left(\frac ne\right)^{\!n}\cdot\left(\frac{n-1}{n}\right)^{\!n}e\end{align*}

In the last step you need to show $$\left(1-\frac 1n\right)^{\!n}=\left(\frac{n-1}n\right)^{\!n}<\frac1e$$ You should know that the limit of this is $e^{-1}=\frac1e$. Then it suffices to show it's increasing in $n$ by a simple usage of the AM-GM inequality: $$\frac{1+(n-1)}{n+1}=\frac{1+\frac{n-1}n+\ldots+\frac{n-1}n}{n+1}>\sqrt[n+1]{1\cdot\left(\frac{n-1}n\right)^{\!n}}\implies\left(\frac n{n+1}\right)^{\!n+1}>\left(\frac{n-1}n\right)^{\!n}$$

Answer 2

Inductive reasoning:

$$n!\leq en(\frac{n}{e})^n=\frac{n^{n+1}}{e^{n-1}}$$

Then must prove

$$(n+1)!=(n+1)n!\leq \frac{(n+1)n^{n+1}}{e^{n-1}} \stackrel{?}{\leq} \frac{(n+1)^{n+2}}{e^n }$$

if and only if:

$$n^{n+1}e<(n+1)^{n+1}$$

$$e<(1+\frac{1}{n})^{n+1}$$

if and only if:

$$ln(e)<(n+1) ln(1+\frac{1}{n})$$ $$1<(n+1) ln(1+\frac{1}{n})$$

The function $(n+1) ln(1+\frac{1}{n})$ is strictly decreasing function and its limit is $e$ so it is always true.

UPDATE

According to this well known limit:

$$\lim_{n \to \infty} (1+\frac{x}{n})^n = e^x$$

In this example, the strictly increasing sequence $(\frac{n-1}{n})^n$ will approach to $e^{-1}$ but it is always below this number and the inequality is valid.

Answer 3

Since $$\log(n!) = \sum_{k=1}^n \log k $$ and the logarithm is an increasing function, $$\log(n!)\leq \int_{1}^{n+1}\log x\,dx = -n+(n+1)\log(n+1) $$ and exponentiating both sides: $$ n! \leq e^{-n} (n+1)^{n+1}$$ so: $$ n! \leq en\cdot e^{-n}n^{n} $$ follows from $n!=n\cdot(n-1)!$.

Answer 4

Here is a proof by indiction, followed by a slight improvement to the inequality for large $n$.

---

OP's inequality: For $n=1$ the inequality holds trivially. Assume the statement holds for some $n\geq1$. Then \begin{align}e(n+1)\Big(\frac{n+1}{e}\Big)^{n+1}&=\frac{n+1}{n}\frac{n+1}{e}\Big(\frac{n+1}{n}\Big)^n en\Big(\frac{n}{e}\Big)^n\\ &=\frac{n+1}{e}\Big(1+\frac1n\Big)^{n+1}en\Big(\frac{n}{e}\Big)^n\\ &>(n+1)\cdot n!=(n+1)! \end{align} Here we have used the fact that $\phi(x)=\Big(1+\frac{1}{x}\Big)^{x+1}$, $x>0$, is strictly monotone decreasing and $\lim_{x\rightarrow\infty}\phi(x)=e$.

---

Slight improvement to OP's inequality: $$n\Big( \frac{n}{e}\Big)^n> n!, \qquad n\geq11$$

We proceed by induction:

Suppose the statement is holds for some $n$ (we check below that $n=11$ does the job). Then \begin{align} (n+1)\Big(\frac{n+1}{e}\Big)^{n+1}&=\frac{n+1}{n}\frac{n+1}{e}\Big(\frac{n+1}{n}\Big)^n n\Big(\frac{n}{e}\Big)^n\\ &= \frac{n+1}{e}\Big(1+\frac{1}{n}\Big)^{n+1}n\Big(\frac{n}{e}\Big)^n\\ &>\frac{n+1}{e}\Big(1+\frac1n\Big)^{n+1}n!>(n+1)! \end{align}

To check the statement for $n=11$, notice that $e<11/4$. Hence $11(11/e)^{11}>11\cdot4^{11}> 11\cdot 10!$

---

Proof that $\phi$ is strictly monotone decreasing for $x>0$: $\phi'(x)=\phi(x)\Big(\log(1+\tfrac1x)-\frac{1}{x}\Big)<0$ since $1+t<e^t$ for all $t\neq0$).