About $n! > (\frac{n}{e})^n$ in "Introduction to Algorithms 3rd Edition" by CLRS.

Question

I am reading "Introduction to Algorithms 3rd Edition" by CLRS.

In Apendix C, the authors use the following inequality:

$n! > (\frac{n}{e})^n$.

My proof of this fact is the following:

1. base case:
   $1! = 1 > \frac{1}{e} = (\frac{1}{e})^1$.
2. induction step:
   Assume that $k! > (\frac{k}{e})^k$.
   Then, $(k+1)! = (k+1) k! \geq (k+1)(\frac{k}{e})^k$.
   By the way, $((1+\frac{1}{k})^k)_{k \in \{1,2, \cdots\}}$ is a monotonic increasing sequence which converges to $e$.
   So, $e > (1+\frac{1}{k})^k$.
   So, $1 > \frac{(1+\frac{1}{k})^k}{e}$.
   So, $k^k > \frac{(k+1)^k}{e}$.
   So, $\frac{(k+1)k^k}{e^k} > \frac{(k+1)^{k+1}}{e^{k+1}}$.
   So, $(k+1)! \geq (k+1)(\frac{k}{e})^k > \frac{(k+1)^{k+1}}{e^{k+1}}$.

On the other hand, obviously, $n^n \geq n!$.

So, $(\frac{n}{1})^n \geq n! > (\frac{n}{e})^n$.

$1 \in\{c | c > 0, n! \in O((\frac{n}{c})^n)\}$.
$e \notin\{c | c > 0, n! \in O((\frac{n}{c})^n)\}$.

My question is here:

What is the value $\sup \{c | c > 0, n! \in O((\frac{n}{c})^n)\}$?

Answer 1

From Stirling’s approximation we have $n!\sim\sqrt{2\pi n}\left(\frac{n}e\right)^n$, so consider

$$\lim_{n\to\infty}\frac{n!}{\left(\frac{n}c\right)^n}=\lim_{n\to\infty}\frac{\sqrt{2\pi n}\left(\frac{n}e\right)^n}{\left(\frac{n}c\right)^n}=\lim_{n\to\infty}\sqrt{2\pi n}\left(\frac{c}e\right)^n\;;$$

this is clearly infinite if $c\ge e$ and $0$ if $0\le c<e$. Thus, $$\sup\left\{c>0:n!\in O\left(\left(\frac{n}c\right)^n\right)\right\}=e\;$$