Stirling's formula furnishes the following asymptotic bound for the factorial:

		(1)
	for every	(2)
		(3)

Proof. [Proof of the upper bound of equation (1)] We must show that for every $\varepsilon > 0$ , we have $$ n! \leq \varepsilon \, n^n \quad \text{for large enough $n$.} $$

To see this, write

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

Proof. [Proof of the lower bound of equation (2)] We are to show that for every $C > 0$ , we have $$ n! \geq C \, n^{\lambda n} \quad \text{for large enough $n$.} $$

We write:

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

Proof. [Proof of bound for $\log n!$ , equation (3)] Showing $\log n! = O (n \log n)$ is simple:

for all $n \geq 1$ .

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

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

Bibliography

1

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, second edition. MIT Press, 2001.

2

Michael Spivak. Calculus, third edition. Publish or Perish, 1994.