14
$\begingroup$

To Prove : $n! > (n/e)^n$

The question seems easy but it ain't; anyone up for it ?

  • 0
    Related question: http://math.stackexchange.com/q/144176/24202015-02-11

5 Answers 5

18

Here's a hint. You assume that $n!>\left(\frac{n}{e}\right)^n$. Now you should show it for n+1, i.e., you should show that $(n+1)! > \left(\frac{n+1}{e}\right)^{n+1}$.

You can write

\begin{equation} (n+1)! > (n+1) \left(\frac{n}{e}\right)^n = (n+1)\left(\frac{n}{n+1}\right)^n \left(\frac{(n+1)^n}{e^n}\right) \end{equation}

Can you solve it from here?

  • 0
    @Ragib: Well, it depends how you define $e$ in the first place. It can be defined as $\lim_{n \to \infty}(1 + \frac{1}{n})^{n},$ after showing that that sequence is increasing, but bounded above, so converges to its least upper bound (then it's clear that this least upper bound, which we call $e$, is greater than $(1+\frac{1}{n})^{n}$ for all integers n).2011-08-22
17

By considering the exponential power series we observe that for $x>0$, $ e^x > \frac{x^n}{n!} $ Now setting $x=n$ we obtain $e^n > \frac{n^n}{n!} $ which rearranges to precisely what is desired. I should note that I had first learned this incredibly short and simple proof of this fact from Qiaochu Yuan's posts on this website, and he in turn attributed it to this article written by Terence Tao.

  • 0
    Nice proof -- Didnt think of problem in this direction -- But then again the main idea was to prove by induction2011-08-21
4

This is the "easy" part of Stirling's formula -- the crude order of magnitude estimate showing how huge $n!$ is, without the $\sqrt{2 \pi n}$ correction that is harder to derive.

Taking logarithms, you are asking for $\log(n!) > n (\log n - 1)$. The latter is the indefinite integral of $\log(n)$. Drawing a picture, this follows from $\log(n)$ being an increasing function. The inequality compares the area under the graph of the function to the area of rectangles underneath the graph. A stronger inequality can be obtained using trapezoids and the convexity of $\log(x)$. I think you can get the $\sqrt{n}$ factor this way but not the exact constant $\sqrt{2 \pi}$.

  • 1
    Just to verify the last statement, it is indeed true that using trapezoids to estimate the area can give us the estimate $n! \sim C n^{n + 1/2} e^{-n} $ for some constant $C$. Then, the "hard" part is to determine $C$, which is commonly done by considering the Wallace product.2011-08-21
2

I had originally written this up for another question but it seems fitting here as well. Maybe this can help someone.

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

1

In an attempt to prove it by induction, you'll reach a stage where you need to prove $\left(1+\frac{1}{n}\right)^n < e.$

Consider the $i^\text{th}$ term in the binomial expansion of $(1+1/n)^n$: $\frac{n!}{(n-i)! i!} \cdot \frac{1}{n^i} < \frac{1}{i!}.$ This is easily provable as the $i^\text{th}$ term is $\frac{n(n-1) \cdots (n-i +1)}{n \cdot n \cdots n} \cdot \frac{1}{i!} < \frac{1}{i!}.$

So, $\left(1 + \frac{1}{n}\right)^n < e.$