# Short and intuitive proof that $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$

The simple inequality that $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$ has a number of different proofs. But is there a particularly intuitive, short and elegant proof that uses the natural interpretation of binomial coefficients, for example. I would ideally like a proof which is also accessible to students with very limited prerequisite knowledge.

Here is the best proof that I have seen which is less intuitive than I was hoping for.

First we first prove that $$\frac{n-i}{k-i} \geq \frac{n}{k}$$ for $i<k\leq n$. This follows from $$0\leq (n-k)i = k(n-i) - n(k-i) = k(k-i)\left(\frac{n-i}{k-i}-\frac{n}{k}\right),$$ and $k(k-i)> 0$, so $(n-i)/(k-i) \geq n/k.$

Now we multiply the over $i\in\{1,\ldots,k-1\}$ to obtain $$\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1} \geq \frac{n^k}{k^k},$$ or equivalently $\binom{n}{k}\geq (n/k)^k$.

-
I'm a little hesitant due to the near-exact wording match compared to this question... – abiessu Sep 25 '13 at 15:33
@abiessu I copied the wording from there to get it right. I hope that is OK. – Anush Sep 25 '13 at 15:34
I'm not in a position to say whether it is okay, but perhaps you could outline a proof that you are aware of so that any answers could focus on improving it. – abiessu Sep 25 '13 at 15:36
What makes you feel that the proof is long? It's pretty straightforward. – Calvin Lin Sep 25 '13 at 15:47
When $k$ divides $n$ then $(n/k)^k$ is the number of ways of choosing $k$ elements with the restriction that only one element is chosen from the range $jk$ to $(j+1)k$. Number of these restricted choices is obviously less than the number of all possible choices. It should be possible to extend this to the case when $k$ doesn't divide $n$ but I haven't found a slick way yet. – Marek Sep 25 '13 at 15:57

## 3 Answers

$n^k$ is the number of ways of picking $k$ balls from $n$ balls with repetition allowed. One can generate all the possible ways by first deciding which $k$ out of $n$ balls to draw and draw from the $k$ selected balls instead. There are $\binom{n}{k}$ ways to choose the $k$ balls and $k^k$ ways to pick from the selected $k$ balls with repetition allowed. This gives us $$n^k \le\binom{n}{k} k^k \quad\iff\quad \left(\frac{n}{k}\right)^k \le \binom{n}{k}$$

-
Right, this counts several times each pick with repetitions, hence the inequality sign. +1. – Did Sep 25 '13 at 16:58
@Did, thanks for fixing my stupid typo. – achille hui Sep 25 '13 at 17:00

Note first that for all $0 \leq i < k \leq n$ we have $k(n-i) = kn - ki > kn - ni =\geq n(k-i)$, and hence $\frac{n-i}{k-i} \geq \frac{n}{k}$. Therefore $${n \choose k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots 1} = \prod_{i=0}^{k-1} \frac{n-i}{k-i} \geq \prod_{i=0}^{k-1} \frac{n}{k} = \left(\frac{n}{k}\right)^k.$$

-
Note that you should still have $\geq$ instead of $>$ since you are allowing for $k=n$. There is also an additional $=$ in $= \geq n(k-i)$. – Calvin Lin Sep 25 '13 at 15:48
This is the same proof OP provided. – Marek Sep 25 '13 at 15:59
@Marek: Looking at the timings, I'm inclined to believe that they did it independently. – Eric Stucky Sep 25 '13 at 16:20

For every $1\leqslant k\leqslant n$ and $0\leqslant i\leqslant k-1$, $$k\leqslant n\implies\frac{i}k\geqslant\frac{i}n\implies 1-\frac{i}k\leqslant1-\frac{i}n.$$ Each term is positive, hence the products are in the same order, that is, $$\frac{k!}{k^k}=\prod_{i=0}^{k-1}\left(1-\frac{i}k\right)\leqslant\prod_{i=0}^{k-1}\left(1-\frac{i}n\right)=\frac{n!}{n^k(n-k)!}.$$ Multiply the leftmost and rightmost terms by $\dfrac{n^k}{k!}$... Et voilà!

-