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

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 3

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 4

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