Solve by induction: $n!>(n/e)^n$

Question

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

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

Answer 1

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?

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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