24
$\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
  • 18
    $\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 '15 at 10:42
31
$\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 '15 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.