Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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
show 3 more comments

3 Answers 3

up vote 10 down vote accepted

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

share|improve this answer
2  
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
add comment

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

share|improve this answer
    
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
1  
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
add comment

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à!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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