Upper bounding n choose k

We want to show that for 1\leq k\leq n, the following holds: {n\choose k} \leq \Big(\frac{n\cdot e}{k}\Big)^k.

First, recall the power series e^k=\sum_{i=0}^\infty{\frac{k^i}{i!}}. For k \geq 1, this sum is definitely larger than its kth term only. In other words, e^k \geq k^k/k!, which implies k! \geq (k/e)^k. Now,

\begin{matrix}{n\choose k}  &=& \frac{n!}{k! \cdot (n-k)!}\\  &=& \frac{n(n-1)(n-2)\cdots (n-(k-1))}{k!}\\  &\leq& \frac{n^k}{k!} \\  &\leq& \frac{n^k}{(k/e)^k} \\  &=& (\frac{en}{k})^k.\\  \end{matrix}

This proof is extracted from the StackExchange discussion here. For more inequalities/bounds for binomial coefficients, see Wikipedia.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s