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 n−ik−i≥nk
Now we multiply the over i∈{1,…,k−1} to obtain n(n−1)⋯(n−k+1)k(k−1)⋯1≥nkkk,
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