Stirling's Formula/Proof 1
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.
Proof
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:
- $\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 {2n + 2 } - \map \ln {2n}\) | Sum of Logarithms | |||||||||||
\(\ds \) | \(=\) | \(\ds \map \ln {2n + 2 } - \map \ln {2n + 1 } + \map \ln {2n + 1 } - \map \ln {2n}\) | adding $0$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \map \ln {\dfrac {2n + 2 }{2n + 1 } } - \map \ln {\dfrac {2n }{2n + 1 } }\) | Difference of Logarithms | |||||||||||
\(\ds \) | \(=\) | \(\ds \map \ln {1 + \frac 1 {2 n + 1} } - \map \ln {1 - \frac 1 {2 n + 1} }\) | set $x = \dfrac 1 {2n + 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 {2n} - 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 {2n} - n \map \ln {\frac n e } } - \paren {\map \ln {\paren {n + 1}!} - \dfrac 1 2 \map \ln {2n + 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 {2n + 2} {2n } } + 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 {2n + 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 {2n + 1 } }^2 } {1 - \paren {\dfrac 1 {2n + 1 } }^2}\) | Sum of Infinite Geometric Sequence | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {\paren {\dfrac 1 {2n + 1 } }^2 } {1 - \paren {\dfrac 1 {2n + 1 } }^2} \dfrac {\paren {2n + 1 }^2} {\paren {2n + 1 }^2}\) | multiplying by $1$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac 1 {\paren {2n + 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 {2n + 1 } \prod_{k \mathop = 1}^n \frac {\paren {2k}^2} {\paren {2 k - 1 }^2 }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \lim_{n \mathop \to \infty} \dfrac 1 {2n + 1 } \prod_{k \mathop = 1}^n \frac {\paren {2k}^2} {\paren {2 k - 1 }^2 } \dfrac {\paren {2k}^2} {\paren {2k}^2}\) | multiplying by $1$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \lim_{n \mathop \to \infty} \dfrac 1 {2n + 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 {2n} e}^{2n} } }^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$