Saturday, April 16, 2016

inequality - Short and intuitive proof that left(fracnkright)kleqbinomnk


The simple inequality that (nk)k(nk) 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 nikink

for $i 0,so(n-i)/(k-i) \geq n/k.$


Now we multiply the over i{1,,k1} to obtain n(n1)(nk+1)k(k1)1nkkk,

or equivalently (nk)(n/k)k.


Answer



nk 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 (nk) ways to choose the k balls and kk ways to pick from the selected k balls with repetition allowed. This gives us nk(nk)kk(nk)k(nk)


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...