Stirling's approximation

Stirling's approximation says that the factorial $n! \sim \sqrt{2\pi n}\,(n/e)^n$ : the ratio of the two sides tends to 1 as $n \to \infty$ . It turns the product $n!$ into a closed form that you can compare with other functions by asymptotic notation. Its weaker consequence, $\lg(n!) = n \lg n - n \lg e + O(\log n)$ , gives the bound $\Omega(n \log n)$ for comparison sorting.

Statement

For each integer $n \ge 1$ there is a real number $r_n$ such that

n! = \sqrt{2\pi n}\,\left(\frac{n}{e}\right)^{n} e^{r_n}, \qquad \frac{1}{12n+1} < r_n < \frac{1}{12n}.

The upper bound and the positivity of $r_n$ are proved below. The lower bound $\frac{1}{12n+1} < r_n$ is Robbins' (1955). So $n! \sim \sqrt{2\pi n}\,(n/e)^n$ in the sense of tilde notation, and $\ln n! = n\ln n - n + \tfrac12\ln n + \tfrac12\ln(2\pi) + r_n$ . The same asymptotic holds for $\Gamma(x+1)$ as $x \to \infty$ through the reals.

The weaker form has a short proof. For each integer $n \ge 1$ ,

\left(\frac{n}{e}\right)^{n} \le n! \le e\sqrt{n}\,\left(\frac{n}{e}\right)^{n},

and so $n\ln n - n \le \ln n! \le n\ln n - n + \tfrac12\ln n + 1$ . In base 2, with $\lg e = 1.4427\ldots$ , we get $n\lg n - n\lg e \le \lg n! \le n\lg n - n\lg e + \tfrac12\lg n + \lg e$ .

In plain words

The number $n!$ is the product of the first $n$ whole numbers. It grows very fast, and the product has no simple form. Stirling's formula gives a simple expression that is close to it. The expression is about the number of items raised to its own power, divided by a power of a fixed constant, times a factor that grows only like the square root of the number.

The formula has two uses. A rough use only needs the size of the logarithm of the product: it is about the number of items times the logarithm of the number of items. This is what the lower bound for sorting needs. A sharp use needs the correction factor too. It says, for example, how many ways there are to choose half of the items, and it does so with a relative error that shrinks as the number of items grows.

Proof

Weak form. We prove $(n/e)^n \le n! \le e\sqrt n\,(n/e)^n$ for each integer $n \ge 1$ .

Lower bound. The series $e^n = \sum_{k \ge 0} n^k/k!$ has positive terms, so $e^n \ge n^n/n!$ . Hence $n! \ge n^n e^{-n} = (n/e)^n$ .

Upper bound. The function $\ln$ is concave on $(0, \infty)$ , so on $[k, k+1]$ it lies above its chord: $\ln x \ge \ln k + (x - k)(\ln(k+1) - \ln k)$ . Integrating over $[k, k+1]$ gives $\int_k^{k+1}\ln x\,dx \ge \frac12(\ln k + \ln(k+1))$ . Add this for $k = 1, \ldots, n-1$ :

\int_1^{n}\ln x\,dx \ge \tfrac12\sum_{k=1}^{n-1}\ln k + \tfrac12\sum_{k=2}^{n}\ln k = \ln n! - \tfrac12\ln n,

where we used $\ln 1 = 0$ . The integral is $n\ln n - n + 1$ . So $\ln n! \le n\ln n - n + 1 + \tfrac12\ln n$ , which is the upper bound. $\square$

This is the technique of integral bounds for sums. It shows that $\ln n! = n\ln n - n + O(\log n)$ , with the error between $0$ and $1 + \frac12\ln n$ .

Sharp form. The proof that $r_n$ exists, that $0 < r_n < \frac{1}{12n}$ , and that the constant is $\sqrt{2\pi}$ is in the proof of the sharp form. It shows that $a_n = \ln n! - (n + \frac12)\ln n + n$ decreases, and that $a_n - \frac{1}{12n}$ increases, so both converge to the same limit. It finds the limit with the Wallis integrals $\int_0^{\pi/2}\sin^m x\,dx$ . The lower bound $r_n > \frac1{12n+1}$ is Robbins' result (1955), and the page does not prove it.

Consequences

The sorting lower bound. A comparison sort on $n$ distinct keys needs a decision tree with at least $n!$ leaves, so its worst case is at least $\lceil \lg n!\rceil$ comparisons, see the comparison sorting lower bound. By the weak form, $\lceil\lg n!\rceil \ge n\lg n - n\lg e \ge n\lg n - 1.4427\,n$ . So the bound is $\Omega(n\log n)$ . The sharp form gives $\lg n! = n\lg n - n\lg e + \tfrac12\lg n + \tfrac12\lg(2\pi) + O(1/n)$ , with $\tfrac12\lg(2\pi) = 1.3257\ldots$ .

The table shows the exact value of $\lg n!$ , the bound $n\lg n - n\lg e$ , and the worst-case comparison count $n\lceil\lg n\rceil - 2^{\lceil\lg n\rceil} + 1$ of merge sort.

$n$	$\lg n!$	$\lceil \lg n! \rceil$	$n\lg n - n\lg e$	merge sort, worst case
10	21.79	22	18.79	25
100	524.76	525	520.12	573
1000	8529.40	8530	8523.09	8977
$10^6$	18488884.82	18488885	18488873.53	18951425

At $n = 10^6$ merge sort is about 2.5 percent above the lower bound. The gap between $\lg n!$ and $n\lg n - n\lg e$ is $\frac12\lg n + 1.3257 + o(1)$ : it is 6.3 at $n = 1000$ and 11.3 at $n = 10^6$ .

$\lg n! = \Theta(n\log n)$ . The upper bound is $\lg n! \le n\lg n$ . For the lower bound, $n\lg n - n\lg e \ge \frac12 n\lg n$ exactly when $\lg n \ge 2\lg e$ , that is $n \ge e^2 = 7.39\ldots$ . So $\frac12 n\lg n \le \lg n! \le n\lg n$ for each $n \ge 8$ . The simpler argument for this fact, which does not need Stirling's formula, is on the page of asymptotic notation.

The central binomial coefficient. Step 6 and Step 7 of the sharp proof give $\binom{2n}{n} \sim 4^n/\sqrt{\pi n}$ . For $n = 10$ this is $187079$ against the true value $184756$ . See also binomial coefficient bounds.

Orders of growth. Since $n! \ge (n/e)^n$ and $(n/e)^n/c^n = (n/(ec))^n \to \infty$ for each constant $c$ , the factorial grows faster than each exponential $c^n$ . Since $n^n/n! \sim e^n/\sqrt{2\pi n} \to \infty$ , it also grows slower than $n^n$ . So $n! = o(n^n)$ , and $n!$ is not $\Theta(n^n)$ . For $n = 10$ , $n^n/n! = 2755.7$ and $e^n/\sqrt{2\pi n} = 2778.8$ .

Tightness

The constant $\sqrt{2\pi}$ and the exponent $\frac12$ of $n$ cannot change: they are the exact limit. The weak upper bound is off by a bounded factor, but the weak lower bound is not. Its upper bound $e\sqrt n\,(n/e)^n$ exceeds the truth by the factor $e/\sqrt{2\pi} = 1.0844\ldots$ in the limit, and its lower bound $(n/e)^n$ is short by the unbounded factor $\sqrt{2\pi n}$ . So the error term $O(\log n)$ in $\ln n! = n\ln n - n + O(\log n)$ cannot be improved to $O(1)$ : the true error is $\frac12\ln n + 0.9189\ldots + O(1/n)$ .

The error exponent $r_n$ is $\sim \frac{1}{12n}$ , by the two-sided bound in the statement. Finer terms are known from the Stirling series:

n! \sim \sqrt{2\pi n}\left(\frac ne\right)^n\left(1 + \frac{1}{12n} + \frac{1}{288n^2} - \frac{139}{51840n^3} + \cdots\right).

For $n = 10$ the factor $\sqrt{2\pi n}(n/e)^n$ is $3598695.6$ , and $10! = 3628800$ . With one, two and three correction terms the value is $3628684.7$ , $3628809.7$ and $3628800.05$ . The series is asymptotic and does not converge for any $n$ .

Two warnings. First, $\sim$ does not mean that the difference is small: $n! - \sqrt{2\pi n}(n/e)^n$ is about $\sqrt{2\pi n}\,(n/e)^n/(12n)$ , which grows without bound. Second, $\ln n! \sim n\ln n$ does not give $n! \sim n^n$ . Taking a logarithm hides a factor of size $e^{-n}$ , as the paragraph on orders of growth shows.

Proof: The sharp form of Stirling's formula, with the constant and the error boundsfull

Statement. There is a real sequence $(r_n)_{n \ge 1}$ with $0 < r_n < \frac{1}{12n}$ for each $n \ge 1$ , such that

n! = \sqrt{2\pi n}\,\left(\frac{n}{e}\right)^n e^{r_n}.

In particular $n! \sim \sqrt{2\pi n}\,(n/e)^n$ . The sharper lower bound $r_n > \frac{1}{12n+1}$ is Robbins' theorem and is not proved here.

Step 1: a convergent sequence. For $n \ge 1$ let

a_n = \ln n! - \left(n + \tfrac12\right)\ln n + n, \qquad\text{so that}\qquad n! = e^{a_n}\sqrt{n}\,(n/e)^n.

Then

a_n - a_{n+1} = \left(n + \tfrac12\right)\ln\frac{n+1}{n} - 1.

To see this, expand $a_{n+1}$ and use $\ln (n+1)! = \ln n! + \ln(n+1)$ : the terms $\ln n!$ cancel, and what remains is $-\ln(n+1) + (n + \frac32)\ln(n+1) - (n+\frac12)\ln n + n - (n+1)$ , which is the right side.

Step 2: a series for the difference. Put $t = \frac{1}{2n+1}$ , so $0 < t < 1$ . Then $\frac{1+t}{1-t} = \frac{2n+2}{2n} = \frac{n+1}{n}$ and $n + \frac12 = \frac{1}{2t}$ . For $0 \le t < 1$ we have $\ln\frac{1+t}{1-t} = 2\sum_{j \ge 0} \frac{t^{2j+1}}{2j+1}$ . So

a_n - a_{n+1} = \frac{1}{2t}\cdot 2\sum_{j \ge 0}\frac{t^{2j+1}}{2j+1} - 1 = \sum_{j \ge 1}\frac{t^{2j}}{2j+1}.

Step 3: two-sided bound on the difference. Every term of the series is positive, so $a_n - a_{n+1} > 0$ . Also $\frac{1}{2j+1} \le \frac13$ for $j \ge 1$ , with strict inequality for $j \ge 2$ , so

a_n - a_{n+1} < \frac13\sum_{j \ge 1} t^{2j} = \frac{t^2}{3(1-t^2)}.

Since $t^{-2} - 1 = (2n+1)^2 - 1 = 4n(n+1)$ , we get $\frac{t^2}{1-t^2} = \frac{1}{4n(n+1)}$ . Hence

0 < a_n - a_{n+1} < \frac{1}{12n(n+1)} = \frac{1}{12n} - \frac{1}{12(n+1)}.

Step 4: the limit and the bounds on $r_n$ . Step 3 says two things. First, $(a_n)$ is strictly decreasing. Second, $a_n - \frac{1}{12n} < a_{n+1} - \frac{1}{12(n+1)}$ , so $b_n = a_n - \frac{1}{12n}$ is strictly increasing. Also $b_n < a_n \le a_1$ for each $n$ , so $(b_n)$ is increasing and bounded above. It converges to a limit $L$ . Since $a_n = b_n + \frac{1}{12n}$ and $\frac1{12n} \to 0$ , the sequence $(a_n)$ also converges to $L$ . A strictly increasing sequence is smaller than its limit, and a strictly decreasing sequence is larger than its limit. So for each $n \ge 1$ ,

L < a_n \quad\text{and}\quad a_n - \frac{1}{12n} < L.

Let $r_n = a_n - L$ . Then $0 < r_n < \frac{1}{12n}$ , and $n! = e^{L} e^{r_n}\sqrt n\,(n/e)^n$ . Put $K = e^L$ . It remains to show $K = \sqrt{2\pi}$ .

Step 5: Wallis integrals. For integers $m \ge 0$ let $I_m = \int_0^{\pi/2}\sin^m x\,dx$ . Then $I_0 = \pi/2$ and $I_1 = 1$ . For $m \ge 2$ write $\sin^m x = \sin^{m-1}x\cdot\sin x$ and integrate by parts: $I_m = (m-1)\int_0^{\pi/2}\sin^{m-2}x\cos^2x\,dx = (m-1)(I_{m-2} - I_m)$ , because the boundary term $-\sin^{m-1}x\cos x$ is 0 at both ends. So $I_m = \frac{m-1}{m}I_{m-2}$ . Since $0 \le \sin x \le 1$ on $[0, \pi/2]$ , the sequence $(I_m)$ is non-increasing. By induction on $m$ , $I_m I_{m+1} = \frac{\pi}{2(m+1)}$ : for $m = 0$ the product is $\pi/2$ , and if it holds for $m$ , then $I_{m+1}I_{m+2} = \frac{m+1}{m+2}I_{m+1}I_m = \frac{\pi}{2(m+2)}$ .

For $n \ge 1$ the monotonicity gives $I_{2n+1} \le I_{2n} \le I_{2n-1}$ . Multiply by $I_{2n} > 0$ :

\frac{\pi}{2(2n+1)} \le I_{2n}^2 \le \frac{\pi}{4n}.

Multiply by $4n/\pi$ : the left side becomes $\frac{2n}{2n+1}$ and the right side becomes 1. Both tend to 1, so $I_{2n}^2 \sim \frac{\pi}{4n}$ , that is $I_{2n} \sim \frac12\sqrt{\pi/n}$ .

Step 6: the central binomial coefficient. The recurrence gives $I_{2n} = \frac\pi2\prod_{j=1}^{n}\frac{2j-1}{2j}$ . Now $\prod_{j=1}^n (2j-1) = \frac{(2n)!}{2^n n!}$ and $\prod_{j=1}^n 2j = 2^n n!$ , so $I_{2n} = \frac{\pi}{2}\cdot\frac{(2n)!}{4^n (n!)^2} = \frac\pi2\binom{2n}{n}4^{-n}$ . With Step 5,

\binom{2n}{n}4^{-n} = \frac{2}{\pi}I_{2n} \sim \frac{2}{\pi}\cdot\frac{\sqrt\pi}{2\sqrt n} = \frac{1}{\sqrt{\pi n}}.

Step 7: the constant. By Step 4, $n! \sim K\sqrt n\,(n/e)^n$ . So $(2n)! \sim K\sqrt{2n}\,(2n/e)^{2n}$ and $(n!)^2 \sim K^2 n\,(n/e)^{2n}$ . Dividing,

\binom{2n}{n} \sim \frac{K\sqrt{2n}\,(2n)^{2n}}{K^2 n\, n^{2n}} = \frac{\sqrt2\,4^n}{K\sqrt n}.

Compare with Step 6: $\frac{\sqrt 2}{K\sqrt n} \sim \frac{1}{\sqrt{\pi n}}$ , so $K = \sqrt{2\pi}$ . Then $n! = \sqrt{2\pi n}\,(n/e)^n e^{r_n}$ with $0 < r_n < \frac1{12n}$ , and $e^{r_n} \to 1$ . $\blacksquare$

Remark. The lower bound $r_n > \frac1{12n+1}$ needs a finer estimate of the series of Step 2. Robbins gives it in the paper cited on the page. The proof above gives the upper bound $\frac{1}{12n}$ and the positivity of $r_n$ .

All proofs on one page

History

The formula is named for James Stirling, who gave it with the constant $\sqrt{2\pi}$ in his book Methodus Differentialis (1730). Abraham de Moivre found the form $n! \sim C\sqrt n\,(n/e)^n$ with the constant $C$ only as a numerical series (Miscellanea Analytica, 1730). Stirling showed that $C = \sqrt{2\pi}$ . Robbins proved the two-sided bound $\frac{1}{12n+1} < r_n < \frac{1}{12n}$ in 1955. Knuth, Volume 1, Section 1.2.11.2, and Graham, Knuth and Patashnik, Chapter 9, derive the formula with the Euler summation formula, and they give the series.

References

https://en.wikipedia.org/wiki/Stirling%27s_approximation, sections History and Speed of convergence and error estimates
Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, fourth edition, Section 3.3, Standard notations and common functions (factorials)
Donald E. Knuth, The Art of Computer Programming, Volume 1, third edition, Section 1.2.11.2, Euler's summation formula (Stirling's approximation)
Graham, Knuth and Patashnik, Concrete Mathematics, second edition, Chapter 9, Asymptotics (Stirling's approximation)
Robert Sedgewick and Kevin Wayne, Algorithms, fourth edition, Section 1.4, Analysis of Algorithms (commonly encountered functions)
Herbert Robbins, A remark on Stirling's formula, American Mathematical Monthly 62 (1955), pages 26 to 29, the bounds 1/(12n+1) < r_n < 1/(12n)

Ladder	Level	What the next level needs
Human proof	H1 sketch	a full proof of correctness
Lean	L0 no Lean part	name a Lean module in the lean field (07)
Visual	V0 none	add viz/scene.ts or a figure (10)
Writing	W4 complete	a review of the text: no review record reviews/CZWG27/text.yaml