0

Prove that $\binom{n}{k} ≥ \left(\frac{n}{k}\right)^k$ for integers $0<k<n $.

I used Stirling formula to find the the combination of the left part but it goes very long and I can not find and thing to analyse that the left part is increasing faster than the right part.

Do you have any idea how to start?

1 Answers1

2

We know that $$ \binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1} = \frac{n^k}{k^k} \frac{(1-1/n)(1-2/n)\cdots(1-(k-1)/n)}{(1-1/k)(1-2/k)\cdots(1-(k-1)/k)}. $$ Since $1-a/n \geq 1-a/k$ for all positive $a$, we conclude that $\binom{n}{k} \geq (n/k)^k$.

Yuval Filmus
  • 57,157