Stirling’s Approximation

Problem 1. Prove that for any $n \in \mathbb N$ ,

$n\log(n) - n < \log(n!) < (n+1) \log(n+1) - n.$

Here, we use $\log \equiv \log_e \equiv \ln$ for brevity.

(Click for Solution)

Solution. For any $n$ , we observe that

$\displaystyle \int_{n-1}^n \log(x)\, \mathrm dx < \log(n) < \int_n^{n+1} \log(x)\, \mathrm dx.$

Summing on both sides, since $\displaystyle \sum_{i=1}^n \log(i) = \log(n!)$ , we have

$\displaystyle \int_0^n \log(x)\, \mathrm dx < \log(n!) < \int_1^{n+1} \log(x)\, \mathrm dx.$

Integrating by parts, $\displaystyle \int \log(x)\, \mathrm dx = x \log(x) - x + C$ , so that taking improper integrals when needed,

$n \log(n) - n < \log(n!) < (n+1) \log(n+1) - (n+1) -(- 1).$

Definition 1. Suppose $f(n), g(n) \neq 0$ for any $n$ . Define

$\displaystyle f(n) \sim g(n) \quad \iff \quad \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1.$

Clearly, for $L \neq 0$ , $f(n) \sim L$ if and only if $\displaystyle \lim_{n \to \infty} f(n) = L$ .

Problem 2. Verify the following properties:

$f(n) \sim f(n)$ .
If $f(n) \sim g(n)$ , then $g(n) \sim f(n)$ .
If $f(n) \sim g(n)$ and $g(n) \sim h(n)$ , then $f(n) \sim h(n)$ .
If $f_1(n) \sim g_1(n)$ and $f_2(n) \sim g_2(n)$ , then $f_1 (n) f_2(n) \sim g_1(n) g_2(n)$ .
If $f_1(n) \sim g_1(n)$ and $f_2(n) \sim g_2(n)$ , then $\displaystyle \frac{f_1(n)}{f_2(n)} \sim \frac{g_1(n)}{g_2(n)}$ .

(Click for Solution)

Solution. Assume all functions are always nonzero. The first identity is obvious:

$\displaystyle \lim_{n \to \infty} \frac{f(n)}{f(n)} = \lim_{n \to \infty} \frac 11 = 1.$

The second identity works due to non-zero-ness of the functions:

$\displaystyle \lim_{n \to \infty} \frac{g(n)}{f(n)} = \lim_{n \to \infty} \frac 1{\frac{f(n)}{g(n)}} = \frac 11 = 1.$

The third identity follows from the limit of a product:

$\displaystyle \lim_{n \to \infty} \frac{f(n)}{h(n)}= \lim_{n \to \infty} \frac{f(n)}{g(n)} \cdot \frac{g(n)}{h(n)} =\lim_{n \to \infty} \frac{f(n)}{g(n)} \cdot \lim_{n \to \infty} \frac{g(n)}{h(n)} = 1 \cdot 1 = 1.$

The fourth identity works like the third:

$\displaystyle \lim_{n \to \infty} \frac{f_1(n) f_2(n)}{g_1(n) g_2(n)} = \lim_{n \to \infty} \frac{f_1(n)}{g_1(n)} \cdot \lim_{n \to \infty} \frac{f_2(n)}{g_2(n)} = 1 \cdot 1 = 1.$

The fifth identity follows from the fourth:

$\displaystyle \lim_{n \to \infty} \frac{f_1(n) / f_2(n)}{g_1(n) / g_2(n)} = \lim_{n \to \infty} \frac{f_1(n)}{g_1(n)} \cdot \lim_{n \to \infty} \frac{g_2(n)}{f_2(n)} = 1 \cdot 1 = 1.$

Problem 3. Prove that the sequence $\{ u_n \}$ defined by

$\displaystyle u_n = \log(n!) - \left(n + \frac 12 \right) \log(n) + n$

converges to some limit $C$ . Deduce that $\displaystyle n! \sim e^C \cdot n^{n+1/2} e^{-n}$ .

(Click for Solution)

Solution. By logarithm properties,

$\begin{aligned} u_n - u_{n+1} &= \left( n + \frac 12 \right) \log \left( \frac{n+1}{n} \right) - 1 \\ &= \left( n + \frac 12 \right) \log \left( \frac{1+\frac 1{2n+1}}{ 1-\frac 1{2n+1} } \right) - 1. \end{aligned}$

Using the Taylor series of $\ln(1+t)$ for $|t| < 1$ ,

$\begin{aligned} \log\left( \frac{1+t}{1-t} \right) &= \log(1+t) - \log(1-t) \\ &= \sum_{k=1}^\infty (-1)^{k+1} \cdot \frac{t^k}{k} - \sum_{k=1}^\infty (-1)^{k+1} \cdot \frac{(-t)^k}{k} \\ &= \sum_{k=1}^\infty (-1)^{k+1} \cdot \frac{t^k}{k} + \sum_{k=1}^\infty \frac{t^k}{k} \\ &= \sum_{k=1}^\infty (1 - (-1)^k) \cdot \frac{t^k}{k} = \sum_{k=0}^\infty \frac{2}{2k+1} \cdot t^{2k+1}. \end{aligned}$

Setting $t = 1/(2n+1)$ ,

$\begin{aligned} u_n - u_{n+1} &= (2n+1) \cdot \frac 12 \log \left( \frac{1+\frac 1{2n+1}}{ 1-\frac 1{2n+1} } \right) - 1 \\ &= (2n+1) \cdot \frac 12 \cdot \sum_{k=0}^\infty \frac{2}{2k+1} \cdot \frac 1{(2n+1)^{2k+1}} - 1 \\ &= \sum_{k=0}^\infty \frac{1}{2k+1} \cdot \frac 1{(2n+1)^{2k}} - 1 \\ &< \frac 13 \cdot \sum_{k=1}^\infty \frac 1{(2n+1)^{2k}} = \frac 13 \cdot \frac 1{(2n+1)^2} \cdot \frac 1{1 - \frac 1{(2n+1)^2}} \\ &= \frac 13 \cdot \frac 1{(2n+1)^2 - 1} = \frac 1{12} \left(\frac 1n - \frac 1{n+1}\right). \end{aligned}$

Therefore $u_n - u_{n+1} > 0$ , so that $\{u_n\}$ is decreasing and $\{u_n - 1/(12n)\}$ is increasing. Since $u_n > u_n - 1/(12n)$ , $u_n$ must be bounded below and converges to some $C \in \mathbb R$ . Hence,

$\displaystyle \frac{n! \cdot e^n}{n^{n+1/2}} = e^{u_n} \sim e^C.$

Dividing by $e^C$ ,

$\displaystyle \lim_{n \to \infty} \frac{n!}{e^C \cdot n^{n+1/2} \cdot e^{-n}} = 1 \quad \Rightarrow \quad n! \sim e^C \cdot n^{n+1/2} e^{-n}.$

Problem 4. Use the Wallis product to evaluate $C$ , and conclude with Stirling’s approximation:

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

(Click for Solution)

Solution. The Wallis product states that

$\displaystyle \lim_{n \to \infty} \frac 1{2n+1} \cdot \prod_{k=1}^n \frac{(2k)^2}{(2k-1)^2} = \frac{\pi}{2}.$

Taking square roots,

$\begin{aligned} \frac 1{\sqrt{ 2n }} \cdot \frac{2^{2n} \cdot (n!)^2 }{(2n)!} &\sim \frac 1{\sqrt{ 2n+1 }} \cdot \frac{2^{2n} \cdot (n!)^2 }{(2n)!}\\ &= \frac 1{\sqrt{ 2n+1 }} \cdot \prod_{k=1}^n \frac{2k}{2k-1} \sim \sqrt{ \frac{\pi}{2} }. \end{aligned}$

We observe that if $f_1(n) \sim g_1(n)$ and $f_2(n) \sim g_2(n)$ and $\displaystyle \lim_{n \to \infty} \frac{g_1(n)}{g_2(n)}$ exists, then

$\begin{aligned} \lim_{n \to \infty} \frac{f_1(n)}{f_2(n)} &= \lim_{n \to \infty} \frac{g_1(n) \cdot \frac{f_1(n)}{g_1(n)}}{g_2(n) \cdot \frac{f_2(n)}{g_2(n)}} \\ &= \lim_{n \to \infty} \frac{g_1(n)}{g_2(n)} \cdot \frac{\displaystyle \lim_{n \to \infty} \frac{f_1(n)}{g_1(n)}}{\displaystyle \lim_{n \to \infty} \frac{f_2(n)}{g_2(n)}} \\ &= \lim_{n \to \infty} \frac{g_1(n)}{g_2(n)} \cdot \frac 11 = \lim_{n \to \infty} \frac{g_1(n)}{g_2(n)}. \end{aligned}$

By Problem 2, $f(n) \sim g(n)$ implies $f(n)^2 \sim g(n)^2$ . Hence, we use the approximation in Problem 3 to derive

$\begin{aligned} \sqrt{\frac{\pi}{2}} \sim \frac 1{\sqrt{ 2n }} \cdot \frac{2^{2n} \cdot (n!)^2 }{(2n)!} &\sim \frac 1{\sqrt{ 2n }} \cdot \frac{2^{2n} \cdot (e^C \cdot n^{n+1/2} \cdot e^{-n})^2 }{e^C \cdot (2n)^{2n+1/2} \cdot e^{-2n}} \\ &=\frac 1{\sqrt{ 2n }} \cdot \frac{2^{2n} \cdot e^{2C} \cdot n^{2n+1} \cdot e^{-2n} }{e^C \cdot 2^{2n} \cdot 2^{1/2} \cdot n^{2n+1/2} \cdot e^{-2n}} \\ &= \frac{ e^{C} }{2}. \end{aligned}$

Therefore, $e^C \sim \sqrt{2\pi}$ . We observe that for nonzero real numbers $L, M$ , $L \sim M$ if and only if $L = M$ . Therefore, $e^C = \sqrt{2\pi}$ , so that