asymptotic bounds for factorial

Stirling’s formula furnishes the following asymptoticbound for the factorial:

$n!=\sqrt{2\pi }{n}^{n+1/2}{e}^{-n}\left(1+\mathrm{\Theta }(\frac{1}{n})\right),n\to \mathrm{\infty }.$

The following less precise bounds are useful for counting purposesin computer science:

$n!$$=o(n^n)$(1)

$n!$(2)

$\log n!$$=\mathrm{\Theta }(n\log n)$(3)

($o$, $\omega$, and $\mathrm{\Theta }$ are Landau notation.)

Proof of the upper bound of equation (1).

We must show that for every $\epsilon >0$, we have

$$n!\le \epsilon n^n\mathit{\hspace{1em}}\text{for large enough }n\text{.}$$

To see this, write

$n!$$=\underbrace{\sqrt{2\pi }{\displaystyle \frac{\sqrt{n}}{e^n}}\left(1+O(\frac{1}{n})\right)}{n}^n,$

and observe that the middle quantity tends to $0$ as$n\to \mathrm{\infty }$,so it can be made smaller than any fixed $\epsilon$by taking $n$ large.∎

Proof of the lower bound of equation (2).

We are to show that for every $C>0$, we have

$$n!\ge C{n}^{\lambda n}\mathit{\hspace{1em}}\text{for large enough }n\text{.}$$

We write:

$n!$$=\underbrace{\sqrt{2\pi n}\left(1+O(\frac{1}{n})\right){\left({\displaystyle \frac{n}{e^{1/(1-\lambda )}}}\right)}^{(1-\lambda )n}}{n}^{\lambda n},$

and the middle expression can be made to be $\ge C$by taking $n$ to be large.∎

Proof of bound for $\log \mathit{}n\mathrm{!}$, equation (3).

Showing $\log n!=O(n\log n)$is simple:

$n!$$=n(n-1)\mathrm{\cdots }(2)(1)\le n^n$

$\log n!$$\le n\log n$

for all $n\ge 1$.

To show $\log n!=\mathrm{\Omega }(n\log n)$,we can take equation (2) with the constants $C=1$and $\lambda =\frac{1}{2}$. Then

$\log n!\ge \frac{1}{2}n\log n$

for large enough $n$. In fact, it may be checked that $n\ge 1$ suffices.∎