Stirling's Formula

From ProofWiki
Jump to navigation Jump to search

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} \left({\frac n e}\right)^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} \left({\frac n e}\right)^n} = 1$


By applying Power Series Expansion for $\ln \left({1 + x}\right)$:

\(\displaystyle \ln \left({\frac {n + 1} n }\right)\) \(=\) \(\displaystyle \ln \left({1 + \frac 1 {2 n + 1} }\right) - \ln \left({1 - \frac 1 {2 n + 1} }\right)\)
\(\displaystyle \) \(=\) \(\displaystyle 2 \sum_{k \mathop = 0}^\infty \frac 1 {2 k + 1} \left({\frac 1 {2 n + 1} }\right)^{2 k + 1}\)


Let $b_n = \ln a_n$.

\(\displaystyle b_n - b_{n + 1}\) \(=\) \(\displaystyle \left({n + \frac 1 2}\right) \ln \left({\frac {n + 1} n}\right) - 1\)
\((1):\quad\) \(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop = 1}^\infty \frac 1 {2 k + 1} \left({\frac 1 {2 n + 1} }\right)^{2 k}\)
\(\displaystyle \) \(>\) \(\displaystyle 0\)
\(\displaystyle b_n\) \(>\) \(\displaystyle b_{n + 1}\)

so the sequence $\left\langle{b_n}\right\rangle$ is (strictly) decreasing.


From $(1)$:

\(\displaystyle b_n - b_{n + 1}\) \(=\) \(\displaystyle \sum_{k \mathop = 1}^\infty \frac 1 {2 k + 1} \left({\frac 1 {2 n + 1} }\right)^{2 k}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle b_n - b_{n + 1}\) \(\lt\) \(\displaystyle \sum_{k \mathop = 1}^\infty \left({\frac 1 {2 n + 1} }\right)^{2 k}\) as $\dfrac 1 {2 k + 1} < 1$
\(\displaystyle \) \(=\) \(\displaystyle \frac 1 {4 n \left({n + 1}\right)}\) Sum of Infinite Geometric Progression


Hence:

\(\displaystyle b_1 - b_n\) \(=\) \(\displaystyle \sum_{m \mathop = 1}^{n - 1} b_m - b_{m + 1}\) Telescoping Series
\(\displaystyle \) \(\lt\) \(\displaystyle \frac 1 4 \sum_{m \mathop = 1}^{n - 1} \frac 1 {m \left({m + 1}\right)}\)
\(\displaystyle \) \(\lt\) \(\displaystyle \frac 1 4 \sum_{m \mathop = 1}^\infty \frac 1 {m \left({m + 1}\right)}\)
\(\displaystyle \) \(=\) \(\displaystyle \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 $\left\langle{b_n}\right\rangle$ is bounded below.


By Monotone Convergence Theorem, it follows that $\left\langle{b_n}\right\rangle$ 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} \left({n!}\right)^4} {\left({\left({2 n}\right)!} \right)^2 \left({2 n + 1}\right)} = \frac \pi 2$


In Part 1 it was proved that:

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


Substituting for $n!$ in $(2)$ yields:

\(\displaystyle \frac \pi 2\) \(=\) \(\displaystyle \lim_{n \mathop \to \infty} \frac {2^{4 n} a^4 \left({4 n^2}\right) n^{4 n} e^{-4 n} } {a^2 \left({4 n}\right) 2^{4 n} n^{4 n} e^{-4 n} \left({2 n + 1}\right)}\)
\(\displaystyle \) \(=\) \(\displaystyle a^2 \lim_{n \mathop \to \infty} \frac n {2 n + 1}\) as most of it cancels out
\(\displaystyle \) \(=\) \(\displaystyle \frac {a^2} 2\)
\(\displaystyle \implies \ \ \) \(\displaystyle a\) \(=\) \(\displaystyle \sqrt \pi\)

Hence the result.

$\blacksquare$


Proof 2

Consider the sequence $\left \langle {d_n} \right \rangle$ defined as:

$\displaystyle d_n = \ln \left({n!}\right) - \left({n + \frac 1 2}\right) \ln n + n$

From Lemma 2 it is seen that $\left \langle {d_n} \right \rangle$ is a decreasing sequence.


From Lemma 3 it is seen that the sequence:

$\left \langle {d_n - \dfrac 1 {12 n}}\right\rangle$

is increasing.

In particular:

$\forall n \in \N_{>0}: d_n - \dfrac 1 {12 n} \ge d_1 = \dfrac 1 {12}$

and so $\left\langle{d_n}\right\rangle$ is bounded below.


From the Monotone Convergence Theorem (Real Analysis), it follows that $\left\langle{d_n}\right\rangle$ 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:

$\displaystyle I_n = \int_0^{\frac \pi 2} \sin^n x \ \mathrm d x$

Then from Lemma 4:

$\displaystyle \lim_{n \mathop \to \infty} \frac {I_{2n} } {I_{2n+1} } = 1$


So:

\(\displaystyle \lim_{n \mathop \to \infty} \dfrac {n!} {n^n \sqrt n e^{-n} }\) \(=\) \(\displaystyle \sqrt {2 \pi}\) Lemma 5
\(\displaystyle \implies \ \ \) \(\displaystyle \lim_{n \mathop \to \infty} \dfrac {n!} {\sqrt{2 \pi n} \left({\frac n e}\right)^n}\) \(=\) \(\displaystyle 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

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