proof of upper and lower bounds to binomial coefficient

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

$$\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.$

Title	proof of upper and lower bounds to binomial coefficient
Canonical name	ProofOfUpperAndLowerBoundsToBinomialCoefficient
Date of creation	2013-03-22 13:49:06
Last modified on	2013-03-22 13:49:06
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	12
Author	rspuzio (6075)
Entry type	Proof
Classification	msc 05A10