Upper Bound on ${n \choose r} $

Question

$$ {n \choose r} \leq \frac{n^n}{r^r ~\cdot~ (n-r)^{(n-r)}} $$

I have a feeling that the above holds but I am not so sure how I go about proving it. Any insights?

Answer 1

One technique for proving statements like this is to prove that the error in the approximation is a multiplicative factor >1. In this case, in the numerator you increase each of the numbers in the set $[n]$ to $n$. In the denominator, you are also increasing $n$-many terms so we can pair them up. Pairing them up cleverly lets you arrive at the conclusion that this holds for $n>4$, and then you can check small cases by hand.

Answer 2

I worked on this a bit more and seems like it can be proved using Stirling's approximation: $$ n! \leq 2\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$$ $$ {n \choose r} = \frac{n!}{r! \cdot (n-r)!} \leq \frac{n^n}{r^r \cdot (n-r)^{(n-r)}} \sqrt{\frac{n}{r \cdot (n-r)}}$$ $$ \leq \frac{n^n}{r^r \cdot (n-r)^{(n-r)}}$$