# Proof for the upper bound and lower bound for binomial coefficients.

I have seen the bounds $\left(\frac{n}{k}\right)^k \leq {n \choose k} \leq \left( \frac{en}{k}\right)^k$ for integers $n \geq k >0$ for the binomial coefficient. I can prove the upper bound in this inequality, but I'm missing some detail for the lower bound. Does anyone know some simple way to prove this lower bound?

• For completion let me put the proof for the upper bound. We know that ${n \choose k} = \frac{n!}{(n-k)! k!} = \frac{n \cdot (n-1) \dots (n-(k-1))}{k!} \leq \frac{n^k}{k!} - (1)$ Now let us look at the expansion of $e^k=\sum_{i=0}^{\infty}\frac{k^i}{i!}$. Now if we just pick the term wrt $k$, we get $e^k > \frac{k^k}{k!}$. Which implies $\frac{1}{k!}< \left(\frac{e}{k}\right)^k$. Now substituting in equation (1), we get the bound. Jul 7, 2015 at 10:42

First, we see that for $k=1$ we have a trivial statement $$\left( \frac{n}{k} \right)^k = n \leq n = \binom{n}{k}.$$

Now, consider $k > 1$ and let $0 < m < k \leq n$. Then

$$k \leq n \Rightarrow \frac{m}{n} \leq \frac{m}{k} \Rightarrow 1 - \frac{m}{k} \leq 1- \frac{m}{n} \Rightarrow \frac{k-m}{k} \leq \frac{n-m}{n} \Rightarrow \frac{n}{k} \leq \frac{n-m}{k-m}$$ Hence, $$\left( \frac{n}{k} \right)^k = \frac{n}{k} \cdot \ldots \cdot \frac{n}{k} \leq \frac{n}{k} \cdot \frac{n-1}{k-1} \cdot \ldots \cdot \frac{n-k+1}{1} = \binom{n}{k}.$$

• Thanks a lot. Very nice proof. Jul 7, 2015 at 10:44

Here's another way:

Take the log of both sides:

$$k(\log n - \log k) \stackrel{show}{\leq} \sum_{i=1}^k \log (n-k+i) - \log i$$

But the expression in the summation on the RHS is decreasing in $$i$$, so it is at least $$k$$ times the minimum value over $$i\leq k$$: $$k (\log n - \log k)$$ which is just the LHS.