proof of upper and lower bounds to binomial coefficient

Let $2\le k\le n$ be natural numbers. We’ll first prove theinequality

$$\left(\genfrac{}{}{0pt}{}{n}{k}\right)\le {\left(\frac{ne}{k}\right)}^k.$$

We rewrite $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ as

$\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)$$=$${\displaystyle \frac{n(n-1)\mathrm{\cdots }(n-k+1)}{k!}}$

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

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

Since all the terms of the series $e^k={\sum }_{n=0}^{\mathrm{\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,

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

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\ge 2\in \mathbb{N}.$$(1)

${\displaystyle \prod _{i=1}^{n-1}}{\left(1+{\displaystyle \frac{1}{i}}\right)}^i$$=$${\displaystyle \prod _{i=1}^{n-1}}{\displaystyle \frac{{(i+1)}^i}{i^i}}$

$=$${\displaystyle \frac{\prod _{i=2}^n{i}^{i-1}}{\left(\prod _{i=1}^{n-1}{i}^{i-1}\right)\cdot (n-1)!}}$

Since each left-hand factor in (1) is , we have.Since , we immediately get

$\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)$$=$

And from

$k\le n$$\iff$$(n-i)\cdot k\ge (k-i)\cdot n\forall \mathrm{\hspace{0.33em}1}\le i\le k-1$

we obtain

$\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)$$=$${\displaystyle \frac{n}{k}}\cdot {\displaystyle \prod _{i=1}^{k-1}}{\displaystyle \frac{n-i}{k-i}}$

$\ge {\left({\displaystyle \frac{n}{k}}\right)}^k.$