Limit of Error in Stirling's Formula
Jump to navigation
Jump to search
Theorem
Consider Stirling's Formula:
- $n! \sim \sqrt {2 \pi n} \paren {\dfrac n e}^n$
The ratio of $n!$ to its approximation $\sqrt {2 \pi n} \paren {\dfrac n e}^n$ is bounded as follows:
- $e^{1 / \paren {12 n + 1} } < \dfrac {n!} {\sqrt {2 \pi n} n^n e^{-n} } < e^{1 / 12 n}$
Proof
Taking the natural logarithm of the ratio of $n!$ to its approximation $\sqrt {2 \pi n} \paren {\dfrac n e}^n$, we obtain:
\(\ds \map \ln {\dfrac {n!} {\sqrt {2 \pi n} n^n e^{-n} } }\) | \(=\) | \(\ds \map \ln {n!} - \map \ln { {\sqrt {2 \pi n} n^n e^{-n} } }\) | Difference of Logarithms | |||||||||||
\(\ds \) | \(=\) | \(\ds \map \ln {n!} - \map \ln {\sqrt {2 \pi} } - \map \ln {\sqrt n} - \map \ln {n^n} - \map \ln {e^{-n} }\) | Sum of Logarithms | |||||||||||
\(\ds \) | \(=\) | \(\ds \map \ln {n!} - \map \ln {\sqrt {2 \pi} } - \dfrac 1 2 \map \ln n- n \map \ln n + n\) | Logarithm of Power, Natural Logarithm of e is 1 | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\ln n! - \paren {n + \dfrac 1 2} \ln n + n} - \map \ln {\sqrt {2 \pi} }\) | rearranging | |||||||||||
\(\ds \) | \(=\) | \(\ds d_n - \map \ln {\sqrt {2 \pi} }\) | letting $d_n := \ln n! - \paren {n + \dfrac 1 2} \ln n + n$ |
From the argument in Stirling's Formula: Proof 2: Lemma 3 we have that $\sequence {d_n - \dfrac 1 {12 n} }$ is an increasing sequence.
Then:
\(\ds d_n - d_{n + 1}\) | \(=\) | \(\ds \ln n! - \paren {n + \frac 1 2} \ln n + n\) | ||||||||||||
\(\ds \) | \(\) | \(\, \ds - \, \) | \(\ds \paren {\ln \paren {n + 1}! - \paren {n + 1 + \frac 1 2} \map \ln {n + 1} + n + 1}\) | |||||||||||
\(\ds \) | \(=\) | \(\ds -\map \ln {n + 1} - \paren {n + \frac 1 2} \ln n + \paren {n + \frac 3 2} \map \ln {n + 1} - 1\) | as $\ln \paren {n + 1}! = \map \ln {n + 1} + \ln n!$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {n + \frac 1 2} \map \ln {\frac {n + 1} n} - 1\) | Difference of Logarithms | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\frac {2 n + 1} 2} \map \ln {\frac {2 n + 2} {2 n} } - 1\) | multiplying top and bottom by $2$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\frac {2 n + 1} 2} \map \ln {\frac {\paren {2 n + 1} + 1} {\paren {2 n + 1} - 1} } - 1\) | adding and subtracting $1$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\frac {2 n + 1} 2} \map \ln {\dfrac {\paren {2 n + 1} } {\paren {2 n + 1} } \times \paren {\frac {1 + \dfrac 1 {2 n + 1} } {1 - \dfrac 1 {2 n + 1} } } } - 1\) | ||||||||||||
\(\text {(1)}: \quad\) | \(\ds \) | \(=\) | \(\ds \paren {\frac {2 n + 1} 2} \map \ln {\frac {1 + \paren {2 n + 1}^{-1} } {1 - \paren {2 n + 1}^{-1} } } - 1\) | dividing top and bottom by $\paren {2 n + 1}$ |
Let:
- $\map f x := \dfrac 1 {2 x} \map \ln {\dfrac {1 + x} {1 - x} } - 1$
for $\size x < 1$.
By Stirling's Formula: Proof 2: Lemma 1:
\(\ds \map f x\) | \(=\) | \(\ds \sum_{n \mathop = 1}^\infty \frac {x^{2 n} } {2 n + 1}\) | Lemma 1 | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac {x^2} 3 + \frac {x^4} 5 + \frac {x^6} 7 + \cdots\) | ||||||||||||
\(\ds \) | \(>\) | \(\ds \frac {x^2} 3 \sum_{n \mathop = 0}^\infty \paren {\dfrac {x^2} 3}^n\) | ||||||||||||
\(\text {(2)}: \quad\) | \(\ds \) | \(>\) | \(\ds \frac {x^2} {3 \paren {1 - \dfrac {x^2} 3} }\) | Sum of Infinite Geometric Sequence |
As $-1 < \dfrac 1 {2 n + 1} < 1$ it can be substituted for $x$ in $(2)$:
\(\ds d_n - d_{n + 1}\) | \(\gt\) | \(\ds \frac {\paren {\paren {2 n + 1}^{-1} }^2} {3 \paren {1 - \dfrac {\paren {\paren {2 n + 1}^{-1} }^2} 3} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {\paren {2 n + 1}^{-1} }^2} {3 \paren {1 - \dfrac {\paren {\paren {2 n + 1}^{-1} }^2} 3} } \times \frac {\paren {2 n + 1}^2} {\paren {2 n + 1}^2}\) | multiplying top and bottom by $\paren {2 n + 1}^2$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {3 \paren {\paren {2 n + 1}^2 - \dfrac 1 3} }\) | simplifying | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {\paren {12 n^2 + 12 n + 2} }\) | ||||||||||||
\(\ds \) | \(>\) | \(\ds \frac 1 {\paren {12 n^2 + 14 n + \dfrac {13} {12} } }\) | key observation | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {12 \paren {n + \dfrac 1 {12} } \paren {n + \dfrac {13} {12} } }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {12} \times \paren {\frac 1 {\paren {n + \dfrac 1 {12} } } - \frac 1 {\paren {n + \dfrac {13} {12} } } }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\frac 1 {12 n + 1} - \frac 1 {12 n + 13} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\frac 1 {12 n + 1} - \frac 1 {12 \paren {n + 1} + 1} }\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds d_n - \frac 1 {12 n + 1}\) | \(>\) | \(\ds d_{n + 1} - \frac 1 {12 \paren {n + 1} + 1}\) |
Therefore the sequence $\sequence {d_n - \dfrac 1 {12 n + 1} }$ is decreasing.
From Stirling's Formula, we have that:
- $\ds \lim_{n \mathop \to \infty} d_n = \ln \sqrt {2 \pi}$
and so:
- $d_n - \dfrac 1 {12 n} < \ln \sqrt {2 \pi} < d_n - \dfrac 1 {12 n + 1}$
for $n = 1, 2, 3, \ldots$
Therefore:
\(\ds - \dfrac 1 {12 n} \ \ \) | \(\, \ds < \, \) | \(\ds -d_n + \ln \sqrt {2 \pi}\) | \(\) | \(\, \ds < \, \) | \(\ds \) | \(\ds - \dfrac 1 {12 n + 1}\) | subtracting $d_n$ throughout | |||||||
\(\ds \dfrac 1 {12 n} \ \ \) | \(\, \ds > \, \) | \(\ds d_n - \ln \sqrt {2 \pi}\) | \(\) | \(\, \ds > \, \) | \(\ds \) | \(\ds \dfrac 1 {12 n + 1}\) | multiplying by $-1$ | |||||||
\(\ds \dfrac 1 {12 n + 1} \ \ \) | \(\, \ds < \, \) | \(\ds d_n - \ln \sqrt {2 \pi}\) | \(\) | \(\, \ds < \, \) | \(\ds \) | \(\ds \dfrac 1 {12 n}\) | switching the order | |||||||
\(\ds e^{1 / \paren {12 n + 1} } \ \ \) | \(\, \ds < \, \) | \(\ds \dfrac {n!} {\sqrt {2 \pi n} n^n e^{-n} }\) | \(\) | \(\, \ds < \, \) | \(\ds \) | \(\ds e^{1 / 12 n}\) | taking exponentials |
$\blacksquare$
Examples
First $10$ Integers
Also see
Sources
- 1977: K.G. Binmore: Mathematical Analysis: A Straightforward Approach ... (previous) ... (next): $\S 17.4 \ (3)$
- 1955: Herbert Robbins: A Remark on Stirling's Formula (Amer. Math. Monthly Vol. 62: pp. 26 – 29) www.jstor.org/stable/2308012