# proof of upper and lower bounds to binomial coefficient

Let $2\leq k\leq n$ be natural numbers. We’ll first prove the inequality

 ${n\choose k}\leq\left(\frac{ne}{k}\right)^{k}.$

We rewrite ${n\choose k}$ as

 $\displaystyle{n\choose k}$ $\displaystyle=$ $\displaystyle\frac{n(n-1)\cdots(n-k+1)}{k!}$ $\displaystyle=$ $\displaystyle\left(1-\frac{1}{n}\right)\cdots\left(1-\frac{k-1}{n}\right)\cdot% \frac{n^{k}}{k!}$

Since each of the parenthesized factors lies between $0$ and $1$, we have

 ${n\choose k}<\frac{n^{k}}{k!}$

Since all the terms of the series $e^{k}=\sum_{n=0}^{\infty}k^{n}/n!$ are positive when $k$ is a positive real number, each term must be smaller than the whole sum; in particular, this implies that, for any non-negative integer $k$, we have $e^{k}>k^{k}/k!$. Rearranging this slightly,

 $1<\frac{k!e^{k}}{k^{k}}$

Multiplying this inequality by the previous inequality for the binomial coefficient yields

 ${n\choose k}<\frac{n^{k}}{k!}\cdot\frac{k!e^{k}}{k^{k}}=\left(\frac{ne}{k}% \right)^{k}$

To conclude the proof we show that

 $\prod_{i=1}^{n-1}\left(1+\frac{1}{i}\right)^{i}=\frac{n^{n}}{n!}\;\forall\;n% \geq 2\in\mathbb{N}.$ (1)
 $\displaystyle\prod_{i=1}^{n-1}\left(1+\frac{1}{i}\right)^{i}$ $\displaystyle=$ $\displaystyle\prod_{i=1}^{n-1}\frac{(i+1)^{i}}{i^{i}}$ $\displaystyle=$ $\displaystyle\frac{\prod\limits_{i=2}^{n}i^{i-1}}{\left(\prod\limits_{i=1}^{n-% 1}i^{i-1}\right)\cdot(n-1)!}$

Since each left-hand factor in (1) is $, we have $\frac{n^{n}}{n!}. Since $n-i, we immediately get

 $\displaystyle{n\choose k}$ $\displaystyle=$ $\displaystyle\frac{\prod\limits_{i=2}^{k-1}\left(1-\frac{1}{i}\right)}{k!}<% \frac{n^{k}}{k!}.$

And from

 $\displaystyle k\leq n$ $\displaystyle\Leftrightarrow$ $\displaystyle(n-i)\cdot k\geq(k-i)\cdot n\;\forall\;1\leq i\leq k-1$

we obtain

 $\displaystyle{n\choose k}$ $\displaystyle=$ $\displaystyle\frac{n}{k}\cdot\prod\limits_{i=1}^{k-1}\frac{n-i}{k-i}$ $\displaystyle\geq\left(\frac{n}{k}\right)^{k}.$
Title proof of upper and lower bounds to binomial coefficient ProofOfUpperAndLowerBoundsToBinomialCoefficient 2013-03-22 13:49:06 2013-03-22 13:49:06 rspuzio (6075) rspuzio (6075) 12 rspuzio (6075) Proof msc 05A10