42
$\begingroup$

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?

$\endgroup$
1
  • 33
    $\begingroup$ 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. $\endgroup$
    – user1105
    Jul 7, 2015 at 10:42

2 Answers 2

43
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks a lot. Very nice proof. $\endgroup$
    – user1105
    Jul 7, 2015 at 10:44
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .