How to prove $(\frac{n+1}{e})^n<n!<e(\frac{n+1}{e})^{n+1}$ without integrating method?

Question

How to prove $$\left(\frac{n+1}{e}\right)^n<n!<e\left(\frac{n+1}{e}\right)^{n+1}$$ without integrating method? In fact we could prove this by noticing that $$i<x<i+1\Rightarrow \ln i<\ln x<\ln (i+1),$$ then integrating it.

Answer 1

Induct - the base case $n = 1$ is trivial. We will show both sides of the equality by looking at ratios; indeed, $\displaystyle\frac{(n+2)^{n+1} e^n}{e^{n+1} (n+1)^n} = \frac{1}{e}\cdot\left(1+\frac{1}{n+1}\right)^{n} \cdot(n+2) < \frac{1}{1+1/(n+1)} \cdot (n+2) = n+1$ since $\left(1 + \frac{1}{n+1}\right)^{n+1} < e.$

Hence, $\left(\frac{n+2}{e}\right)^{n+1} < \left(\frac{n+1}{e}\right)^{n}\cdot (n+1) < n!\cdot (n+1) = (n+1)!$ by hypothesis. For the other side, the ratio is $\displaystyle\frac{1}{e}\cdot \left(1 + \frac{1}{n+1}\right)^{n+1}\cdot(n+2)$; it suffices to show that this is greater than $n+1.$ That is, $\displaystyle \frac{1}{e}\cdot\left(\frac{n+2}{n+1}\right)^{n+1} > \frac{n+1}{n+2},$ which is equivalent to $\left(1+ \frac{1}{n+1}\right)^{n+2} > e.$ To prove this, we use the fact that $\ln (1+h) > \frac{h}{1+h}.$ Then $(n+2)\ln\left(1+\frac{1}{n+1}\right) > (n+2)\frac{1/(n+1)}{(n+2)/(n+1)} = 1,$ whence the desired inequality follows.

Answer 2

I'll enhance an earlier answer of mine and show that $e(n/e)^n < n! < e^{3/2}\sqrt{n}(n/e)^n$.

This is better than OP's request since $((n+1)/e)^n < e(n/e)^n$ is the same as $(1+1/n)^n < e$ and $e^{3/2}\sqrt{n}(n/e)^n <e((n+1)/e)^{n+1}$ is the same as $e\sqrt{e/n}<(1+1/n)^{n+1}$ which is more than true since $(1+1/n)^{n+1} > e$ (proofs available upon request).

The only result from analysis we need is $z-z^2/2 < \ln(1+z) < z$ for $0 < z < 1$.

We first bound $H_n = \sum_{k=1}^{n} 1/k$.

$\begin{align} H_n &= \sum_{k=1}^{n} 1/k\\ &> \sum_{k=1}^{n} (\ln(1+1/k))\\ &= \sum_{k=1}^{n} (\ln(k+1)-\ln(k))\\ &= \ln(n+1)\\ \end{align} $

and

$\begin{align} H_n &= \sum_{k=1}^{n} 1/k\\ &< \sum_{k=1}^{n} (\ln(1+1/k) -1/(2k^2))\\ &= \sum_{k=1}^{n} (\ln(k+1)-\ln(k)) - (1/2)\sum_{k=1}^{n} 1/k^2\\ &= \ln(n+1)- (1/2)\sum_{k=1}^{n} 1/k^2\\ \end{align} $.

To bound the right-hand sum

$\begin{align} \sum_{k=1}^{n} 1/k^2 &=1+\sum_{k=2}^{n} 1/k^2\\ &<1+\sum_{k=2}^{n} 1/(k(k-1))\\ &=1+\sum_{k=2}^{n} (1/(k-1)-1/k)\\ &=1+1-1/n\\ &< 2\\ \end{align} $

so $\ln(n+1)< H_n< \ln(n+1)+1$.

We start with $\ln(n!) = \sum_{k=1}^n \ln k$ and estimate $\ln k$.

$\begin{align} (x+1)\ln(x+1)-x \ln x &= x(\ln(x+1)-\ln(x))+\ln(x+1)\\ &=x\ln(1+1/x)+\ln(x+1)\\ \end{align} $

so $ (x+1)\ln(x+1)-x \ln x -\ln(x+1)=x\ln(1+1/x)$.

Using this, $x\ln(1+1/x) <x(1/x) = 1 $ and $x\ln(1+1/x) >x(1/x-1/(2x^2) =1-1/(2x) $ so $1-1/(2x) < (x+1)\ln(x+1)-x \ln x -\ln(x+1) < 1$. Note that this is just an approximate form of $\int \ln x\,dx = x \ln x - x$ or $\ln x = (x \ln x)' - 1$.

Summing for $x$ from 1 to $n-1$, $n-1-\sum_{k=1}^{n-1} 1/(2k) < \sum_{x=1}^{n-1} \big((x+1)\ln(x+1)-x \ln x -\ln(x+1)\big) < n-1 $ or $n-1-H_{n-1}/2 < \sum_{x=1}^{n-1} \big((x+1)\ln(x+1)-x \ln x -\ln(x+1)\big) < n-1 $

Since the left part of the sum is telescoping and the right part gives $\ln(n!)$, $n-1-H_{n-1}/2 < n \ln n -\ln(n!) < n-1$.

Using the right side, $\ln(n!) > n \ln n-n+1$ or $n! > e(n/e)^n$.

Using the left side, $\ln(n!) < n \ln n-n+1+H_{n-1}/2 < n \ln n-n+1+(\ln(n)+1)/2 $ or $n! < e^{3/2}\sqrt{n}(n/e)^n$.

By taking more terms of the expansion of $\ln(1+1/z)$, we can get the asymptotic series for $\ln(n!)$, which is Stirling's formula without the constant.

Answer 3

The left hand inequality is immediate from the power series for $e^x$. Plugging in $x = n+1$ gives $$e^{n+1} = \sum_{m=0}^{\infty} {(n+1)^m \over m!} > {(n+1)^{n+1} \over (n+1)!}$$ $$= {(n+1)^n \over n!}$$ This rearranges into the left inequality.