2
$\begingroup$

How can we prove that $\left(\frac{n}{k}\right)^k\le \binom{n}{k}$
I try with induction but I don't get the result I want.

$\endgroup$
5
$\begingroup$

I'm going to assume that $k \neq 0$, thus $k\geq 1$

$\left(\frac{n}{k}\right)^k = \underbrace{\frac{n}{k}\frac{n}{k}\cdots \frac{n}{k}}_{\text{k-terms}}$

$\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}$ from which $\frac{n-i}{k-i} \geq \frac{n}{k}$ for $0 \leq i \leq k-1$.

It's unclear whether you need a combinatorial proof or not, induction doesn't constitute a combinatorial proof, and combinatorial proofs tend to verify that two different ways of counting things are equal, but you have an inequality. In any case here is a direct proof.

$\endgroup$
4
$\begingroup$

First multiply both sides by the denominator of the LHS. Then the new RHS gives you the number of ways in which you select k out of n people and hand them k balls one by one, with no restriction to the number one man can receive. The new LHS gives you the number of ways to hand k balls to n people without the restrictions.

But note that whenever you included person A on the RHS, you counted the situation of him receiving all the k balls all those times. On the LHS you counted this situation only once. Similarly for any number of balls. Thus the RHS is always greater than LHS, unless k=1 when you have equality, and you get the reason why.

$\endgroup$

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