TAOCP 1.2.6 Exercise 45

Section 1.2.6: Binomial Coefficients

Exercise 45. [HM21] Using the generalized binomial coefficient suggested in exercise 42, find

$$ \lim_{r \to \infty}\frac{\binom{r}{k}}{r^k}. $$

Verified: no
Solve time: -

Solution

By equation (3),

$$ \binom{r}{k} = \frac{r(r-1)\cdots(r-k+1)}{k!}, \qquad \text{integer } k \ge 0. $$

Hence

$$ \frac{\binom{r}{k}}{r^k} = \frac{r(r-1)\cdots(r-k+1)}{k!,r^k} = \frac1{k!} \prod_{j=0}^{k-1}\left(1-\frac{j}{r}\right). $$

Here $k$ is fixed. For each $j$ with $0\le j\le k-1$,

$$ \lim_{r\to\infty}\left(1-\frac{j}{r}\right)=1. $$

Since the product contains exactly $k$ factors,

$$ \lim_{r\to\infty} \prod_{j=0}^{k-1}\left(1-\frac{j}{r}\right) = \prod_{j=0}^{k-1}1 = 1. $$

Therefore

$$ \lim_{r\to\infty}\frac{\binom{r}{k}}{r^k} = \frac1{k!}. $$

Thus the required limit is

$$ \boxed{\frac1{k!}}. $$