Binomial coefficients

We give an estimate to the binomial coefficients. It is easy to see that ${n \choose k} \leq n^k$, but we can in fact prove a much stronger upper bound.

Theorem 30

$(n/k)^k \leq {n \choose k} \leq (en/k)^k$

Proof:

The first inequality is quite easy to see (left as an exercise). To see ${n \choose k} \leq (en/k)^k$, we use the binomial theorem to first say that $(1+x)^n > {n \choose k} x^k$ for every positive real $x$. Using the inequality $(1+x) \leq e^x$, we have

${n \choose k} x^k < e^{xn}$

After that, we plug in $x = (k/n) > 0$, which gives

${n \choose k} (k/n)^k < e^k$

Rearranging the terms leads to the desired result.