TAOCP 1.2.5 Exercise 8

Section 1.2.5: Permutations and Factorials

Exercise 8. [**] [HM15] Show that the limit in Eq. (13) does equal $n!$ when $n$ is a nonnegative integer.

Verified: yes
Solve time: 1m12s

Let

$$ L_m=\frac{m^n m!}{(n+1)(n+2)\cdots(n+m)}. $$

Assume that $n$ is a nonnegative integer. Since

$$ (n+1)(n+2)\cdots(n+m) =\frac{(n+m)!}{n!}, $$

we have

$$ L_m=\frac{m!,m^n,n!}{(n+m)!} =\frac{n! , m^n}{(m+1)(m+2)\cdots(m+n)}. $$

Therefore

$$ \frac{L_m}{n!} =\prod_{k=1}^{n}\frac{m}{m+k} =\prod_{k=1}^{n}\frac{1}{1+k/m}. $$

For each fixed $k$, $\frac{1}{1+k/m}\to1$ as $m\to\infty$. Since the product contains exactly $n$ factors, where $n$ is fixed,

$$ \lim_{m\to\infty}\frac{L_m}{n!} =\prod_{k=1}^{n}\lim_{m\to\infty}\frac{1}{1+k/m} =1. $$

Hence

$$ \lim_{m\to\infty}L_m=n!, $$

which is precisely Eq. (13) for nonnegative integers $n$. Thus the limit in Eq. (13) agrees with the ordinary factorial function whenever $n$ is a nonnegative integer.

This completes the proof.

∎