# Proving upper bound for $\binom{n}{k}$ directly from given fact

Given the fact: for every $n\in\mathbb{N}$ $$e\left (\frac{n}{e}\right)^n\leq n!\leq en\left (\frac{n}{e}\right)^n$$ Prove directly: $$\binom{n}{k}\leq \left (\frac{en}{k}\right )^k$$

Yes, this inequality is as obvious as obvious gets ($\binom{n}{k}\leq \frac{n^k}{k^k}$), but how do we utilize fact to come to desired result?
Have attempted to manipulate the upper/lower bounds of $n!$ so that we get: $$\frac{1}{k!}\geq \frac{1}{e}\left (\frac{e}{k}\right )^k\qquad \frac{1}{(n-k)!}\geq\frac{1}{e}\left (\frac{e}{n-k}\right)^{n-k}$$ combined, results in $$en\left (\frac{n}{e}\right)^n\cdot \frac{1}{e}\left (\frac{e}{k}\right )^k\cdot \frac{1}{e}\left (\frac{e}{n-k}\right)^{n-k}\geq \binom{n}{k}$$ If we extract the part of interest from the above product, we may ask: $$\left (\frac{en}{k}\right )^k\overset{?}\geq \frac{1}{n^k}\left (\frac{n}{e}\right )^{n+1}\left (\frac{e}{n-k}\right )^{n-k}\cdot \left (\frac{en}{k}\right )^k\geq \binom{n}{k}$$ Hence, we ask whether: $$n^{n-k+1}\leq e^{k+1}(n-k)^{n-k}$$ i.e remains to show for $1\leq k\leq n$ $$n\left (\frac{n}{n-k}\right )^{n-k}\leq e^{k+1}$$

Unnecessary work. Begin by evaluating one piece at a time.

Don't expand out all three factorials.

We have

$$\binom {n}{k} = \frac {n^{\underline k}}{k!} \le \frac {n^k}{k!}\;.$$

Now we use the bounds on the factorial, but only for $k$. $$k! \ge e \left( \frac {k}{e} \right)^k \ge \left ( \frac {k}{e} \right)^k \Rightarrow \frac {1}{k!} \le \left( \frac{e}{k}\right)^k.$$

Putting this together, $\binom {n}{k} \le \left ( \frac {ne}{k} \right)^k$, as desired.

This was a bit tricky, since the factorial bounds were given in terms of $n$, though they were only needed for $k$, and because they were stronger than what was needed. In asymptotic calculations, most of the art is realising what you can safely ignore.

• Many thanks, overthinking is bad :< – Alvin Lepik Sep 14 '16 at 7:03
• Haha yes, if you try to be too precise, the expressions get very ugly. This is a simple but surprisingly good bound, as there is a lower bound of $\left ( \frac {n}{k} \right)^k$, which isn't so far off. – Shagnik Sep 14 '16 at 7:05