Limit of Error in Stirling's Formula

From ProofWiki
Jump to: navigation, search

Theorem

Consider Stirling's Formula:

$n! \sim \sqrt {2 \pi n} \left({\dfrac n e}\right)^n$

The ratio of $n!$ to its approximation $\sqrt {2 \pi n} \left({\dfrac n e}\right)^n$ is bounded as follows:

$e^{1 / \left({12 n + 1}\right)} \le \dfrac {n!} {\sqrt {2 \pi n} n^n e^{-n} } \le e^{1 / 12 n}$


Proof

Let $d_n = \ln n! - \left({n + \dfrac 1 2}\right) \ln n + n$.

From the argument in Stirling's Formula: Proof 2: Lemma 3 we have that $\left\langle{d_n - \dfrac 1 {12 n} }\right\rangle$ is an increasing sequence.


Then:

\(\displaystyle d_n - d_{n+1}\) \(=\) \(\displaystyle \ln \left({n!}\right) - \left({n + \frac 1 2}\right) \ln n + n\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\, \displaystyle - \, \) \(\displaystyle \left({\ln \left({\left({n+1}\right)!}\right) - \left({n + 1 + \frac 1 2}\right) \ln \left({n + 1}\right) + n + 1}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle - \ln \left({n+1}\right) - \left({n + \frac 1 2}\right) \ln n + \left({n + \frac 3 2}\right) \ln \left({n+1}\right) - 1\) $\quad$ (as $\ln \left({\left({n+1}\right)!}\right) = \ln \left({n+1}\right) + \ln \left({n!}\right)$) $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({n + \frac 1 2}\right) \ln \left({\frac {n+1} n}\right) - 1\) $\quad$ $\quad$
\((1):\quad\) \(\displaystyle \) \(=\) \(\displaystyle \frac {2n + 1} 2 \ln \left({\frac {1 + \left({2n + 1}\right)^{-1} } {1 - \left({2n + 1}\right)^{-1} } }\right) - 1\) $\quad$ $\quad$


Let:

$f \left({x}\right) := \dfrac 1 {2 x} \ln \left({\dfrac {1 + x} {1 - x} }\right) - 1$

for $\left\vert{x}\right\vert < 1$.


By Stirling's Formula: Proof 2: Lemma 1:

\(\displaystyle f \left({x}\right)\) \(=\) \(\displaystyle \sum_{k \mathop = 1}^\infty \frac {x^{2n} } {2n + 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {x^2} 3 + \frac {x^4} 5 + \frac {x^6} 7 + \cdots\) $\quad$ $\quad$
\(\displaystyle \) \(>\) \(\displaystyle \frac {x^2} 3\) $\quad$ $\quad$


$\displaystyle f \left({x}\right) = \sum_{k \mathop = 1}^\infty \frac {x^{2n} } {2n + 1}$

As $-1 < \dfrac 1 {2n + 1} < 1$ it can be substituted for $x$ from $(1)$:

\(\displaystyle d_n - d_{n+1}\) \(>\) \(\displaystyle \frac 1 3 \frac 1 {\left({2n + 1}\right)^2}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac 1 {12 n^2 + 12 n + 3}\) $\quad$ $\quad$


Next:

\(\displaystyle \frac 1 {12 n + 1} - \frac 1 {12 \left({n + 1}\right) + 1}\) \(=\) \(\displaystyle \frac {12 n + 13 - 12 n - 1} {\left({12 n + 1}\right) \left({12 n + 13}\right)}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {12} {\left({12 n + 1}\right) \left({12 n + 13}\right)}\) $\quad$ $\quad$


It follows that:

\(\displaystyle \) \(\) \(\displaystyle \left({d_n - \frac 1 {12 n + 1} }\right) - \left({\frac 1 {12 \left({n + 1}\right) + 1} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(>\) \(\displaystyle \frac {\left({12 n + 1}\right) \left({12 n + 13}\right) - 12 \left({12 n^2 + 12 n + 3}\right)} {3 \left({12 n + 1}\right) \left({12 n + 13}\right) \left({2n + 1}\right)^2}\) $\quad$ $\quad$

The numerator equals:

$12 n \left({14 - 12}\right) + \left({13 - 36}\right) = 24 n - 23 > 0$

for $n = 1, 2, 3, \ldots$

Therefore the sequence $\left\langle{d_n - \dfrac 1 {12 n + 1} }\right\rangle$ is decreasing.

From Stirling's Formula, we have that:

$\displaystyle \lim_{n \to \infty} d_n = d$

where $d = \ln \left({\sqrt{2 \pi} }\right)$

and so:

$d_n - \dfrac 1 {12 n} < d < d_n - \dfrac 1 {12 n + 1}$

for $n = 1, 2, 3, \ldots$

Taking exponentials, and again from Stirling's Formula:

$e^{-1/12n} < \dfrac {\left({\sqrt{2n} }\right) n^{n + 1/2} e^{-n} } {n!} < e^{-1/\left({12n + 1}\right)}$

from whence the result.

$\blacksquare$


Sources