1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Many thanks, overthinking is bad :< $\endgroup$ – Alvin Lepik Sep 14 '16 at 7:03
  • $\begingroup$ 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. $\endgroup$ – Shagnik Sep 14 '16 at 7:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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