Saturday, April 16, 2016

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


Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...