Prove with integration the inequality $e(\frac{n}{e})^n < n! < n \times e(\frac{n}{e})^n$

Question

Prove with integration the inequality, I need some advice about how to start prove it.
I know that if function is Monotonically increasing function so :
$$ f(1)+\int^n_1f(x)dx\leq f(1)+f(2)+....+f(n)\leq f(n)+\int^n_1f(x)dx$$

$$e(\frac{n}{e})^n < n! < n \times e(\frac{n}{e})^n$$

Thanks!

The symbol for $\times$ is $\mathtt{\backslash times}$ – wlad Apr 17 '15 at 07:50 — wlad, Apr 17 '15 at 07:50
Or you could use $\mathtt{\backslash cdot}$ for $\cdot$ – wlad Apr 17 '15 at 08:11 — wlad, Apr 17 '15 at 08:11

Peter Košinár · Answer 1 · 2013-05-23T08:05:19.077

3

Hint 1: Logarithm is your friend; it turns products into sums.

Hint 2: $\ln(n!)=\sum\limits_{i=1}^n \ln i$. Thus, $f(x)=\ln(x)$ might be a good candidate for trying to apply the inequalities you have listed.

edited May 23 '13 at 08:05

answered May 23 '13 at 06:48

Peter Košinár

10,810

still dont find how to solve it. what is the function to work with here? – Ofir Attia May 23 '13 at 07:06
@OfirAttia: If your $n!$ is too large, you can use Stirling's Approximation. – Inceptio May 23 '13 at 07:11

jim · Answer 2 · 2013-05-23T07:31:06.307

3

try to show : $$ n \log n - n + 1 \leq \log (n!) \leq (n + 1)\log n - n + 1 \ldots(1)$$

using $\log(x)$ over$[1,n]$ taking the integer partition of $[1,n]$

lower sum of $\int^n_1\log(x)dx=\log2+\log3+\ldots+\log(n-1)=\log(n-1)!$

similarly compute the upper sum and then

lower sum $\leq \int^n_1\log(x)dx \leq$ upper sum.

Then take exponential of $(1)$ to get the result.

edited May 23 '13 at 07:31

answered May 23 '13 at 07:20

jim

3,624

score 2 · Answer 3 · edited Apr 17 '15 at 08:05

Two important inequalities:

$e^{-x} \geq 1-x$
$e^{x} \geq 1+x$

Proof for 1. $g(x) = e^{-x}-1+x \implies g'(x) = 1-e^{-x} \geq 0 \forall x$ so $g(x) \geq g(0)$ for $x \geq 0 \implies e^{-x} \geq 1-x $

Proof for 2. $g(x) = e^{x}-1-x \implies g'(x) = e^{x}-1 \geq 0 \forall x \geq0 $

Let $x = \frac{1}{y}$ Using 1, $e^{-\frac{1}{y}} \geq 1-\frac{1}{y}$ $\implies$ $\frac{1}{e} \geq (1-\frac{1}{y})^y \cdots (3)$

Let $x=\frac{1}{y-1}$ then using 2, $e^{\frac{1}{y-1}} \geq 1+\frac{1}{y-1}$ $\implies$ $e^{-\frac{1}{y-1}} \leq \frac{y-1}{y} \implies \frac{1}{e} \leq (1-\frac{1}{y})^{{y-1}} \cdots (4)$

From 3,4: $$ (1-\frac{1}{y})^y \leq \frac{1}{e} \leq (1-\frac{1}{y})^{y-1} \cdots(5) $$

Now, assume truth for : $e(\frac{n}{e})^n \leq n! \leq n \times e(\frac{n}{e})^n$

True for $n=1$?: $1 \leq 1 \leq 1$

Assume truth for $n=k-1$: $e(\frac{k-1}{e})^{k-1} \leq (k-1)! \leq k \times e(\frac{k-1}{e})^{k-1} \cdots(6)$

Multiple (6) by $k$: $$ k \times e(\frac{k-1}{e})^{k-1} \leq k! \leq k \times k \times e(\frac{k-1}{e})^{k-1} $$

Thus, $$ k^k \times e \times e^{-k} \times [e(1-\frac{1}{k})^{k-1}] \leq k! \leq k^k \times k \times e \times e^{-k} \times [e(1-\frac{1}{k})^{k}] ..\cdots (7) $$ From (5):

$e(1-\frac{1}{k})^k \leq 1 \leq e(1-\frac{1}{k})^{k-1}$

Notice the terms in square brackets

Thus, from (5) and (7):

$$ k^k \times e \times e^{-k} \leq k! \leq k^k \times k \times e \times e^{-k} \implies e(\frac{k}{e})^k \leq k! \leq k \times e(\frac{k}{e})^k $$

score 2 · Answer 4 · answered Aug 15 '15 at 08:27

If you plug in $f(x)=\ln(x)$ into your inequality, you get:

$$ \ln(1) + \int_1^n\ln(x)dx \leq \ln(1)+\cdots+\ln(n) \leq \ln(n)+\int_1^n\ln(x)dx $$ Now, $\ln(1)+\cdots+\ln(n)=\ln(n!)$. Also $\int_1^n\ln(x)dx=n\ln(n)-n+1$ Thus, the inequality becomes: $$ n\ln(n)-n+1 \leq \ln(n!) \leq \ln(n)+n\ln(n)-n+1$$ If you now take the ineqality and raise e to the power of each side (which we can do because $e^x$ is monotonically increasing), and using the fact that $e^{n\ln(n)}=n^n$, we get: $$ n^n\cdot\frac1{e^n}\cdot e \leq n! \leq n\cdot n^n \cdot \frac1{e^n}\cdot e$$

And this simplifies to the desired inequality.

score 1 · Answer 5 · answered May 20 '17 at 00:10

Depending on how you introduced $e$, you might be able to use the fact that there are two sequences $(a_n)_{n \in \mathbb{N}}$, $(b_n)_{n \in \mathbb{N}}$ with

$$\begin{align} a_n ~~~&:=~~~ \left ( 1 + \frac{1}{n} \right ) ^n \\ ~ \\ b_n ~~~&:=~~~ \left ( 1 - \frac{1}{n} \right ) ^{-n} \end{align}$$

and

$$\underset{n \rightarrow \infty}{\lim} a_n ~~~=~~~ \underset{n \rightarrow \infty}{\lim} b_n ~~~=~~~ e \\ ~ \\$$

While both sequences converge to the same limit, $a_n$ approaches from the bottom and $b_n$ approaches from the top:

import numpy as np
import matplotlib.pyplot as plt
from matplotlib import rcParams
rcParams.update({'figure.autolayout': True})

pts = np.arange(0, 20, 1)
a_n = lambda n: (1+1/n)**n
b_n = lambda n: (1-1/n)**(-n)

plt.errorbar(x = pts, xerr = None, y = a_n(pts), yerr = None, fmt = "bx", markersize = "5", markeredgewidth = "2", label = "$a_n$")
plt.errorbar(x = pts, xerr = None, y = b_n(pts), yerr = None, fmt = "rx", markersize = "5", markeredgewidth = "2", label = "$b_n$")
plt.plot(pts, [np.exp(1)]*len(pts), color = "black", linewidth = 2, label = "$e$")
plt.xlim(1.5, 14.5)
plt.ylim(2.0, 3.5)
plt.legend(loc = "best")
plt.setp(plt.gca().get_legend().get_texts(), fontsize = "22")
plt.show()

So we're going to use the following inequality:

$$\forall n \in \mathbb{N} ~ : ~~~~~ \left ( 1 + \frac{1}{n} \right ) ^n ~~~~<~~~~ e ~~~~<~~~~ \left ( 1 - \frac{1}{n} \right ) ^{-n} \tag*{$\circledast$} \\ ~ \\$$

Thesis

$$\forall n \in \mathbb{N}, ~ n \geq 2 ~ : ~~~~~ e \cdot \left ( \frac{n}{e} \right )^n ~~~~<~~~~ n! ~~~~<~~~~ n \cdot e \cdot \left ( \frac{n}{e} \right )^n \\ ~ \\$$

Proof By Induction

Base Case

We begin with $n = 2$ and get

$$\begin{align} & ~ && e \cdot \left ( \frac{2}{e} \right )^2 ~~~~&&<~~~~ 2! ~~~~&&<~~~~ 2 \cdot e \cdot \left ( \frac{2}{e} \right )^2 \\ ~ \\ & \Leftrightarrow && e \cdot \frac{4}{e^2} ~~~~&&<~~~~ 1 \cdot 2 ~~~~&&<~~~~ 2 \cdot e \cdot \frac{4}{e^2} \\ ~ \\ & \Leftrightarrow && \frac{4}{e} ~~~~&&<~~~~ 2 ~~~~&&<~~~~ \frac{8}{e} \\ ~ \\ &\Leftrightarrow && 2 ~~~~&&<~~~~ e ~~~~&&<~~~~ 4 ~~~~ \\ \end{align} $$

Which is a true statement.

Inductive Hypothesis

Therefore the statement holds for some $n$. $\tag*{$\text{I.H.}$}$

Inductive Step

$$\begin{align} & ~ && e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \\ ~ \\ & = && (n+1) \cdot \frac{1}{e} \cdot e \cdot \left ( \frac{n+1}{e} \right )^n\\ ~ \\ & = && (n+1) \cdot \left ( \frac{n}{e} \right )^n \cdot \left ( \frac{n+1}{n} \right )^n\\ ~ \\ & = && (n+1) \cdot \left ( \frac{n}{e} \right )^n \cdot \left ( 1 + \frac{1}{n} \right )^n\\ ~ \\ & \overset{\circledast}{<} && (n+1) \cdot \left ( \frac{n}{e} \right )^n \cdot e\\ ~ \\ & \overset{\text{I.H.}}{<} && (n+1) \cdot n!\\ ~ \\ & = && (n+1)!\\ ~ \\ & = && (n+1) \cdot n!\\ ~ \\ & \overset{\text{I.H.}}{<} && (n+1) \cdot n \cdot e \cdot \left ( \frac{n}{e} \right )^n\\ ~ \\ & = && (n+1) \cdot e \cdot \left ( \frac{n}{e} \right )^{n+1} \cdot e \\ ~ \\ & = && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \cdot \left ( \frac{n}{n+1} \right )^{n+1} \cdot e \\ ~ \\ & = && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \cdot \left ( 1 - \frac{1}{n+1} \right )^{n+1} \cdot e \\ ~ \\ & \overset{\circledast}{<} && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \cdot \left ( 1 - \frac{1}{n+1} \right )^{n+1} \cdot \left ( 1 - \frac{1}{n+1} \right )^{-(n+1)} \\ ~ \\ & = && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \\ ~ \\ \end{align} $$

Conclusion

Therefore the statement holds $\forall n \in \mathbb{N}, ~ n \geq 2$. $$\tag*{$\square$}$$

Prove with integration the inequality $e(\frac{n}{e})^n < n! < n \times e(\frac{n}{e})^n$

5 Answers5

Linked