TAOCP 1.2.6 Exercise 67

Exercise 67. [M20] Prove the upper bound

$$ \binom{n}{k} \le \left(\frac{ne}{k}\right)^k, \qquad n \ge k \ge 0. $$

Verified: no
Solve time: -

Solution

We begin with the definition of the binomial coefficient for integers $n \ge k \ge 0$:

$$ \binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1} = \frac{n!}{k!(n-k)!}. \tag{5} $$

Consider the product representation

$$ \binom{n}{k} = \frac{n}{1} \cdot \frac{n-1}{2} \cdot \frac{n-2}{3} \cdots \frac{n-k+1}{k} = \prod_{j=1}^{k} \frac{n-j+1}{j}. \tag{3} $$

We aim to show that each factor satisfies

$$ \frac{n-j+1}{j} \le \frac{n}{j}. $$

Indeed, for $1 \le j \le k$ we have $n-j+1 \le n$, and $j>0$, so division preserves the inequality. Consequently,

$$ \prod_{j=1}^{k} \frac{n-j+1}{j} \le \prod_{j=1}^{k} \frac{n}{j} = \frac{n^k}{k!}. $$

Next, we apply the standard bound for factorials, valid for all integers $k \ge 1$:

$$ k! \ge \left(\frac{k}{e}\right)^k. \tag{*} $$

This inequality follows from Stirling's formula:

$$ k! = \sqrt{2\pi k}\left(\frac{k}{e}\right)^k e^{\theta_k/(12k)}, \quad 0 < \theta_k < 1, $$

from which $k! \ge (k/e)^k$ immediately. Taking reciprocals preserves the inequality:

$$ \frac{1}{k!} \le \left(\frac{e}{k}\right)^k. $$

Combining these bounds, we obtain

$$ \binom{n}{k} = \prod_{j=1}^{k} \frac{n-j+1}{j} \le \frac{n^k}{k!} \le n^k \left(\frac{e}{k}\right)^k = \left(\frac{ne}{k}\right)^k. $$

Hence the desired inequality holds for all integers $n \ge k \ge 0$:

$$ \boxed{\binom{n}{k} \le \left(\frac{ne}{k}\right)^k}. $$

This completes the proof.

∎