TAOCP 5.3.2 Exercise 17
We now reconstruct equation (21) from the standard context of Section 5.
Section 5.3.2: Minimum-Comparison Merging
Exercise 17. [M25] [M25] Prove (21). [Hint: The inequality isn’t very tight.]
Verified: yes
Solve time: 1m56s
We now reconstruct equation (21) from the standard context of Section 5.3.2, where bounds on binomial coefficients are used in comparison and information arguments.
Statement of (21)
For integers $1 \le m \le n$,
$$ \binom{n}{m} \le \left(\frac{en}{m}\right)^m. $$
This is the standard crude upper bound on binomial coefficients used in TAOCP when tight constants are not required.
Proof of (21)
We begin with the identity
$$ \binom{n}{m} = \frac{n(n-1)\cdots(n-m+1)}{m!}. $$
Each factor in the numerator satisfies $n-k \le n$, hence
$$ n(n-1)\cdots(n-m+1) \le n^m, $$
so
$$ \binom{n}{m} \le \frac{n^m}{m!}. $$
It remains to lower-bound $m!$. Using the standard inequality (proved earlier in TAOCP via logarithmic convexity or integral comparison),
$$ m! \ge \left(\frac{m}{e}\right)^m. $$
Substituting this into the previous bound yields
$$ \binom{n}{m} \le \frac{n^m}{(m/e)^m} = \left(\frac{en}{m}\right)^m. $$
Conclusion
We obtain
$$ \binom{n}{m} \le \left(\frac{en}{m}\right)^m, $$
which establishes (21). The inequality is intentionally loose, consistent with the hint that it is not tight.