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! = \sqrt {2 \pi n} \paren {\dfrac n e}^n \paren {1 + \dfrac 1 {12 n} + \map \OO {\dfrac 1 {n^2} } }$


Proof 1

Let $a_n = \dfrac {n!} {\sqrt {2 n} \paren {\frac n e}^n}$.


Part 1

It will be shown that:

$\ds \lim_{n \mathop \to \infty} a_n = a$

for some constant $a$.

This will imply that:

$\ds \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 {n + 1} - \map \ln n\) Difference of Logarithms
\(\ds \) \(=\) \(\ds \map \ln {n + 1} + \map \ln 2 - \map \ln 2 - \map \ln n\) adding $0$
\(\ds \) \(=\) \(\ds \map \ln {2 n + 2} - \map \ln {2 n}\) Sum of Logarithms
\(\ds \) \(=\) \(\ds \map \ln {2 n + 2} - \map \ln {2 n + 1} + \map \ln {2 n + 1} - \map \ln {2 n}\) adding $0$
\(\ds \) \(=\) \(\ds \map \ln {\dfrac {2 n + 2} {2 n + 1} } - \map \ln {\dfrac {2 n} {2 n + 1} }\) Difference of Logarithms
\(\ds \) \(=\) \(\ds \map \ln {1 + \frac 1 {2 n + 1} } - \map \ln {1 - \frac 1 {2 n + 1} }\) setting $x = \dfrac 1 {2 n + 1}$
\(\ds \) \(=\) \(\ds \sum_{k \mathop = 1}^\infty \paren {-1}^{k - 1} \frac 1 k {\paren {\frac 1 {2 n + 1} }^k} - \paren {-\sum_{k \mathop = 1}^\infty \frac 1 k {\paren {\frac 1 {2 n + 1} }^k} }\) Power Series Expansion for Logarithm of 1 + x and Power Series Expansion for Logarithm of 1 + x: Corollary
\(\ds \) \(=\) \(\ds 2 \sum_{k \mathop = 0}^\infty \frac 1 {2 k + 1} \paren {\frac 1 {2 n + 1} }^{2 k + 1}\) even terms cancel out; odd terms doubled


Let $b_n = \ln a_n$.

\(\ds b_n\) \(=\) \(\ds \map \ln {\dfrac {n!} {\sqrt {2 n} \paren {\frac n e}^n} }\)
\(\ds \) \(=\) \(\ds \map \ln {n!} - \dfrac 1 2 \map \ln {2 n} - n \map \ln {\frac n e}\) Sum of Logarithms and Difference of Logarithms
\(\ds b_n - b_{n + 1}\) \(=\) \(\ds \paren {\map \ln {n!} - \dfrac 1 2 \map \ln {2 n} - n \map \ln {\frac n e} } - \paren {\map \ln {\paren {n + 1}!} - \dfrac 1 2 \map \ln {2 n + 2} - \paren {n + 1} \map \ln {\frac {n + 1} e} }\)
\(\ds \) \(=\) \(\ds \map \ln {\dfrac {n!} {\paren {n + 1}!} } + \dfrac 1 2 \map \ln {\dfrac {2 n + 2} {2 n} } + n \map \ln {\frac {n + 1} n} + \map \ln {n + 1} - \map \ln e\) Sum of Logarithms and Difference of Logarithms
\(\ds \) \(=\) \(\ds n \map \ln {\frac {n + 1} n} + \dfrac 1 2 \map \ln {\dfrac {n + 1} n} - \map \ln {n + 1} + \map \ln {n + 1} - \map \ln e\) rearranging
\(\ds \) \(=\) \(\ds \paren {n + \frac 1 2} \map \ln {\frac {n + 1} n} - 1\)
\(\ds \) \(=\) \(\ds \paren {n + \frac 1 2} 2 \sum_{k \mathop = 0}^\infty \frac 1 {2 k + 1} \paren {\frac 1 {2 n + 1} }^{2 k + 1} - 1\) substituting from above and Power Series Expansion for Logarithm of 1 + x
\(\ds \) \(=\) \(\ds \paren {2 n + 1} \sum_{k \mathop = 0}^\infty \frac 1 {2 k + 1} \paren {\frac 1 {2 n + 1} }^{2 k + 1} - 1\)
\(\text {(1)}: \quad\) \(\ds \) \(=\) \(\ds \sum_{k \mathop = 1}^\infty \frac 1 {2 k + 1} \paren {\frac 1 {2 n + 1} }^{2 k}\) canceling $k = 0$ from sum
\(\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 \dfrac {\paren {\dfrac 1 {2 n + 1} }^2} {1 - \paren {\dfrac 1 {2 n + 1} }^2}\) Sum of Infinite Geometric Sequence
\(\ds \) \(=\) \(\ds \dfrac {\paren {\dfrac 1 {2 n + 1} }^2} {1 - \paren {\dfrac 1 {2 n + 1} }^2} \dfrac {\paren {2 n + 1}^2} {\paren {2 n + 1}^2}\) multiplying by $1$
\(\ds \) \(=\) \(\ds \dfrac 1 {\paren {2 n + 1}^2 - 1}\)
\(\ds \) \(=\) \(\ds \frac 1 {4 n \paren {n + 1} }\)


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} }\) from above
\(\ds \) \(<\) \(\ds \frac 1 4 \sum_{m \mathop = 1}^\infty \frac 1 {m \paren {m + 1} }\) all the way to $\infty$
\(\ds \) \(=\) \(\ds \frac 1 4\) Sum of Sequence of Products of Consecutive Reciprocals

and so:

\(\ds b_1\) \(=\) \(\ds \map \ln {1!} - \dfrac 1 2 \map \ln 2 - \map \ln {\frac 1 e}\)
\(\ds \) \(=\) \(\ds 1 - \dfrac 1 2 \map \ln 2\)

and:

$b_1 - b_n < \dfrac 1 4$

Therefore:

$b_n > b_1 - \dfrac 1 4 = \dfrac 3 4 - \dfrac 1 2 \map \ln 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:

$\ds \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:

\(\ds \frac \pi 2\) \(=\) \(\ds \prod_{k \mathop = 1}^\infty \frac {2 k} {2 k - 1} \cdot \frac {2 k} {2 k + 1}\)
\(\ds \) \(=\) \(\ds \prod \paren {\frac 2 1 \cdot \frac 2 3} \paren {\frac 4 3 \cdot \frac 4 5} \paren {\frac 6 5 \cdot \frac 6 7} \cdots\)
\(\ds \) \(=\) \(\ds \lim_{n \mathop \to \infty} \dfrac 1 {2 n + 1} \prod_{k \mathop = 1}^n \frac {\paren {2 k}^2} {\paren {2 k - 1}^2}\)
\(\ds \) \(=\) \(\ds \lim_{n \mathop \to \infty} \dfrac 1 {2 n + 1} \prod_{k \mathop = 1}^n \frac {\paren {2 k}^2} {\paren {2 k - 1}^2} \dfrac {\paren {2 k}^2} {\paren {2 k}^2}\) multiplying by $1$
\(\ds \) \(=\) \(\ds \lim_{n \mathop \to \infty} \dfrac 1 {2 n + 1} \prod_{k \mathop = 1}^n \frac {2^4 k^4} {\paren {\paren {2 k - 1} \paren {2 k} }^2}\)
\(\text {(2)}: \quad\) \(\ds \) \(=\) \(\ds \lim_{n \mathop \to \infty} \frac {2^{4 n} \paren {n!}^4} {\paren {\paren {2 n}!}^2 \paren {2 n + 1} }\)


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} \paren {n!}^4} {\paren {\paren {2 n}!}^2 \paren {2 n + 1} }\)
\(\ds \) \(=\) \(\ds \lim_{n \mathop \to \infty} \frac {2^{4 n} \paren {a \sqrt {2 n} \paren {\dfrac n e}^n}^4} {\paren {\paren {a \sqrt {4 n} \paren {\dfrac {2 n} e}^{2 n} } }^2 \paren {2 n + 1} }\)
\(\ds \) \(=\) \(\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} }\) Power of Power
\(\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$


Proof 3

From Poisson Distribution Approximated by Normal Distribution, we have:

Let $X$ be a discrete random variable which has the Poisson distribution $\Poisson \lambda$.

Then for large $\lambda$:

$\Poisson \lambda \approx \Gaussian \lambda \lambda$

where $\Gaussian \lambda \lambda$ denotes the normal distribution.


Since the Poisson Distribution with parameter $\lambda$ converges to the Normal Distribution with mean $\lambda$ and variance $\lambda$, their density functions will be asymptotically equal.


$\dfrac 1 {k!} \lambda^k e^{-\lambda} \approx \dfrac 1 {\sqrt {2 \pi \lambda} } \map \exp {-\dfrac {\paren {k - \lambda}^2} {2 \lambda} }$


Evaluating this expression at the mean simplifies to the expression:

$\dfrac 1 {\lambda!} \lambda^\lambda e^{-\lambda} \approx \dfrac 1 {\sqrt {2 \pi \lambda} }$

Rearranging, we obtain:

$\lambda! \approx \sqrt {2 \pi \lambda} \lambda^\lambda e^{-\lambda}$

$\blacksquare$


Also defined as

Stirling's formula can also be seen reported variously as:

\(\ds n!\) \(\sim\) \(\ds \sqrt {2 \pi} \, n^n n^{1/2} e^{-n}\)
\(\ds n!\) \(\sim\) \(\ds n^n e^{-n} \sqrt {2 \pi n}\)
\(\ds n!\) \(\sim\) \(\ds \sqrt {2 \pi n} \, n^n e^{-n}\)


Other variants are sometimes encountered, for example:

$\ds \lim_{n \mathop \to \infty} \dfrac {n!} {e^{-n} n^n \sqrt {2 \pi n} } = 1$


Also known as

Stirling's formula is otherwise known as Stirling's approximation.

Some refer to it as Stirling's asymptotic formula.


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=741594"