Limit of Error in Stirling's Formula

From ProofWiki
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

Stirling-robbins.png



Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Limit_of_Error_in_Stirling%27s_Formula&oldid=741127"