# How to lower/upper bound $n!$ using $1+x\leq e^x$?

I need to prove for all positive integer $n$

$$e\left(\frac{n}{e}\right)^n\leq n!\leq en\left(\frac{n}{e}\right)^n,$$ using the hint $1+x\leq e^x$ for all $x\in \mathbb{R}$.

I did this:

The hint says

• for $x=0$, $1\leq 1$;
• for $x=1$, $2\leq e$;
• ...
• for $x=n-1$, $n\leq e^{n-1}$.

So I multiplied these $n$ inequalities to get

$$n!\leq e^{n-1+\ldots+1},$$ or $$n!\leq e^{\frac{n(n-1)}{2}},$$ and I get stuck there.

• I will edit to let $n$ be positive. – Zir Jan 15 '17 at 0:15
• Oh, whoops, was I supposed to use $1+x\le e^x$? – Simply Beautiful Art Jan 15 '17 at 0:39
• Yes, that was the hint I am supposed to use. – Zir Jan 15 '17 at 0:44
• Bleh, well, whatever XD. – Simply Beautiful Art Jan 15 '17 at 1:33

Rearranging gives the equivalent inequalities $$1 \le (n-1)! \left(\frac{e}{n}\right)^{n-1} \le n.$$

When $n=1$ both inequalities are equalities. Assuming the statement holds for $n=k$, then we want to prove $$1 \le k! \left(\frac{e}{k+1}\right)^k \le k+1.$$

The first inequality holds since $$k! \left(\frac{e}{k+1}\right)^k = \underbrace{e \cdot \left(\frac{k}{k+1}\right)^k}_{\ge 1} \cdot \underbrace{(k-1)! \left(\frac{e}{k}\right)^{k-1}}_{\ge 1 \text{ by induction}}$$ where the first term is $\ge 1$ because the hint gives $$e^{1/k} \frac{k}{k+1} \ge \left(1+\frac{1}{k}\right) \frac{k}{k+1} = 1.$$

The second inequality is due to $$k! \left(\frac{e}{k+1}\right)^k = \underbrace{e \cdot \left(\frac{k}{k+1}\right)^k}_{\le \frac{k+1}{k}} \cdot \underbrace{(k-1)! \left(\frac{e}{k}\right)^{k-1}}_{\le k \text{ by induction}}$$ where the first term is $\le \frac{k+1}{k}$ because $$e \cdot \left(\frac{k}{k+1}\right)^{k+1} = e \cdot \left(1-\frac{1}{k+1}\right)^{k+1} \le e \cdot e^{-1} = 1.$$ [It is well known that $\left(1-\frac{1}{k+1}\right)^{k+1}$ converges to $e^{-1}$ as $k \to \infty$, but one can show by induction that this actually increases monotonically to $e^{-1}$.]

• Thanks. In fact the last one is also due using the hint by setting $x=-\frac{1}{k+1}$ in $1+x\leq e^x$. – Zir Jan 15 '17 at 2:43

Take the log of all sides, so we just need to prove that

$$n\ln n-n+1\le\ln(n!)\le (n+1)\ln n-n+1$$

Then, it is easy to see that

$$\ln(n!)=\sum_{k=1}^n\ln(k)$$

And that is the right Riemann sum to the following integral:

$$\sum_{k=1}^n\ln(k)\ge\int_1^n\ln(x)\ dx=n\ln n-n+1$$

So we have proven the left side. Then notice that we have the following trapezoidal sum:

$$\frac{\ln(n)+2\ln((n-1)!)}2=\frac{\ln(n!)+\ln((n-1)!)}2\\=\sum_{k=1}^n\frac{\ln(k+1)+\ln(k)}2\\\le\int_1^n\ln(x)\ dx=n\ln(n)-n+1\\\frac{\ln(n)+2\ln((n-1)!)}2\le n\ln(n)-n+1\\\implies\ln((n-1)!)\le\left(n-\frac12\right)\ln(n)-n+1\\\implies\ln(n!)=\ln(n)+\ln((n-1)!)\le\left(n+\frac12\right)\ln(n)-n+1$$

Thus, when $n\ge1$,

$$\ln(n!)\le\left(n+\frac12\right)\ln(n)-n+1\le(n+1)\ln(n)-n+1$$

and we have everything we wanted.