Stirling's Formula
Theorem
The factorial function can be approximated by the formula:
- $n! \sim \sqrt {2 \pi n} \paren {\dfrac n e}^n$
where $\sim$ denotes asymptotically equal.
Refinement
A refinement of Stirling's Formula is:
- $n! \sim \sqrt {2 \pi n} \paren {\dfrac n e}^n \paren {1 + \dfrac 1 {12 n} }$
Proof 1
Let $a_n = \dfrac {n!} {\sqrt {2 n} \paren {\frac n e}^n}$.
Part 1
It will be shown that:
- $\lim_{n \mathop \to \infty} a_n = a$
for some constant $a$.
This will imply that:
- $\displaystyle \lim_{n \mathop \to \infty} \frac {n!} {a \sqrt{2 n} \paren {\frac n e}^n} = 1$
By applying Power Series Expansion for $\map \ln {1 + x}$:
\(\ds \map \ln {\frac {n + 1} n}\) | \(=\) | \(\ds \map \ln {1 + \frac 1 {2 n + 1} } - \map \ln {1 - \frac 1 {2 n + 1} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 2 \sum_{k \mathop = 0}^\infty \frac 1 {2 k + 1} \paren {\frac 1 {2 n + 1} }^{2 k + 1}\) |
Let $b_n = \ln a_n$.
\(\ds b_n - b_{n + 1}\) | \(=\) | \(\ds \paren {n + \frac 1 2} \map \ln {\frac {n + 1} n} - 1\) | ||||||||||||
\(\text {(1)}: \quad\) | \(\ds \) | \(=\) | \(\ds \sum_{k \mathop = 1}^\infty \frac 1 {2 k + 1} \paren {\frac 1 {2 n + 1} }^{2 k}\) | |||||||||||
\(\ds \) | \(>\) | \(\ds 0\) | ||||||||||||
\(\ds b_n\) | \(>\) | \(\ds b_{n + 1}\) |
so the sequence $\sequence {b_n}$ is (strictly) decreasing.
From $(1)$:
\(\ds b_n - b_{n + 1}\) | \(=\) | \(\ds \sum_{k \mathop = 1}^\infty \frac 1 {2 k + 1} \paren {\frac 1 {2 n + 1} }^{2 k}\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds b_n - b_{n + 1}\) | \(<\) | \(\ds \sum_{k \mathop = 1}^\infty \paren {\frac 1 {2 n + 1} }^{2 k}\) | as $\dfrac 1 {2 k + 1} < 1$ | ||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {4 n \paren {n + 1} }\) | Sum of Infinite Geometric Sequence |
Hence:
\(\ds b_1 - b_n\) | \(=\) | \(\ds \sum_{m \mathop = 1}^{n - 1} b_m - b_{m + 1}\) | Definition of Telescoping Series | |||||||||||
\(\ds \) | \(<\) | \(\ds \frac 1 4 \sum_{m \mathop = 1}^{n - 1} \frac 1 {m \paren {m + 1} }\) | ||||||||||||
\(\ds \) | \(<\) | \(\ds \frac 1 4 \sum_{m \mathop = 1}^\infty \frac 1 {m \paren {m + 1} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 4\) | Sum of Sequence of Products of Consecutive Reciprocals |
and so:
- $b_n > b_1 - \dfrac 1 4 = \dfrac 3 4 - \dfrac {\ln 2} 2$
Thus by definition $\sequence {b_n}$ is bounded below.
By Monotone Convergence Theorem, it follows that $\sequence {b_n}$ is convergent.
Let $b$ denote its limit.
Then:
- $\displaystyle \lim_{n \mathop \to \infty} a_n = e^{\lim_{n \mathop \to \infty} b_n} = e^b = a$
as required.
$\Box$
Part 2
By Wallis's Product, we have:
- $\displaystyle \prod_{n \mathop = 1}^\infty \frac {2 n} {2 n - 1} \cdot \frac {2 n} {2 n + 1} = \frac \pi 2$
or equivalently:
- $(2): \quad \displaystyle \lim_{n \mathop \to \infty} \frac {2^{4 n} \paren {n!}^4} {\paren {\paren {2 n}!}^2 \paren {2 n + 1} } = \frac \pi 2$
In Part 1 it was proved that:
- $n! \sim a \sqrt {2 n} \paren {\dfrac n e}^n$
Substituting for $n!$ in $(2)$ yields:
\(\ds \frac \pi 2\) | \(=\) | \(\ds \lim_{n \mathop \to \infty} \frac {2^{4 n} a^4 \paren {4 n^2} n^{4 n} e^{-4 n} } {a^2 \paren {4 n} 2^{4 n} n^{4 n} e^{-4 n} \paren {2 n + 1} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds a^2 \lim_{n \mathop \to \infty} \frac n {2 n + 1}\) | as most of it cancels out | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {a^2} 2\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds a\) | \(=\) | \(\ds \sqrt \pi\) |
Hence the result.
$\blacksquare$
Proof 2
Consider the sequence $\sequence {d_n}$ defined as:
- $d_n = \map \ln {n!} - \paren {n + \dfrac 1 2} \ln n + n$
From Lemma 2 it is seen that $\sequence {d_n}$ is a decreasing sequence.
From Lemma 3 it is seen that the sequence:
- $\sequence {d_n - \dfrac 1 {12 n} }$
is increasing.
In particular:
- $\forall n \in \N_{>0}: d_n - \dfrac 1 {12 n} \ge d_1 = \dfrac 1 {12}$
and so $\sequence {d_n}$ is bounded below.
From the Monotone Convergence Theorem (Real Analysis), it follows that $\sequence {d_n}$ is convergent.
Let $d_n \to d$ as $n \to \infty$.
From Exponential Function is Continuous, we have:
- $\exp d_n \to \exp d$ as $n \to \infty$
Let $C = \exp d$.
Then:
- $\dfrac {n!} {n^n \sqrt n e^{-n} } \to C$ as $n \to \infty$
It remains to be shown that $C = \sqrt {2 \pi}$.
Let $I_n$ be defined as:
- $\ds I_n = \int_0^{\frac \pi 2} \sin^n x \rd x$
Then from Lemma 4:
- $\ds \lim_{n \mathop \to \infty} \frac {I_{2 n} } {I_{2 n + 1} } = 1$
So:
\(\ds \lim_{n \mathop \to \infty} \dfrac {n!} {n^n \sqrt n e^{-n} }\) | \(=\) | \(\ds \sqrt {2 \pi}\) | Lemma 5 | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \lim_{n \mathop \to \infty} \dfrac {n!} {\sqrt {2 \pi n} \paren {\frac n e}^n}\) | \(=\) | \(\ds 1\) |
Hence the result.
$\blacksquare$
Also defined as
This result can also be seen reported as:
- $n! \sim \sqrt {2 \pi} n^n n^{1/2} e^{-n}$
Other variants are sometimes encountered.
Also known as
Stirling's Formula is otherwise known as Stirling's approximation.
Examples
Factorial of $8$
The factorial of $8$ is given by Stirling's Formula as:
- $8! \approx 39 \ 902$
which shows an error of about $1 \%$.
Also see
Source of Name
This entry was named for James Stirling.
Sources
- 1965: Murray R. Spiegel: Theory and Problems of Laplace Transforms ... (previous) ... (next): Chapter $1$: The Laplace Transform: Some Special Functions: $\text {I}$. The Gamma function: $4$
- 1968: Murray R. Spiegel: Mathematical Handbook of Formulas and Tables ... (previous) ... (next): $16.16$: Asymptotic Expansions for the Gamma Function
- 1970: N.G. de Bruijn: Asymptotic Methods in Analysis (3rd ed.) ... (previous) ... (next): $1.1$ What is asymptotics? $(1.1.1)$
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $2 \cdotp 506 \, 628 \ldots$
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $24$
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.5$: Permutations and Factorials: $(7)$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $2 \cdotp 50662 \, 8 \ldots$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $24$
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Entry: Stirling's Formula
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Entry: Stirling's Formula