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} \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

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