Prove the inequality $\sum^m_{k=0} {n\choose k}\leq \left ( \frac{en}{m} \right)^m$

Question

When doing some exercises in probability, I was faced with the question to prove the following inequality: $$\sum^m_{k=0} {n\choose k}\leq \left ( \frac{en}{m} \right)^m, \forall m\leq n \in \mathbb N$$

I was not able to come up with a solution, but found this one here. The thing is, the exercise came with the following tip: "multiply both sides by $(m/n)^m$, replace this by $(m/n)^k$ on the lhs, and use the binomial theorem".

I was wondering if someone was able to prove this inequality actually using this tip.

Answer 1

Multiplying

$$\sum_{k=0}^m\binom{n}k\le\left(\frac{en}m\right)^m$$

on both sides by $\left(\frac{m}n\right)^m$ results in the equivalent inequality

$$\left(\frac{m}n\right)^m\sum_{k=0}^m\binom{n}k\le\left(\frac{m}n\right)^m\left(\frac{en}m\right)^m=e^m\;.$$

Now

$$\begin{align*} \left(\frac{m}n\right)^m\sum_{k=0}^m\binom{n}k&=\sum_{k=0}^m\left(\frac{m}n\right)^m\binom{n}k\\ &\le\sum_{k=0}^m\left(\frac{m}n\right)^k\binom{n}k\quad\left(\text{since }\frac{m}n\le 1\right)\\ &\le\sum_{k=0}^n\left(\frac{m}n\right)^k\binom{n}k\\ &=\left(1+\frac{m}n\right)^n\\ &\le e^{\frac{m}n\cdot n}=e^m\;, \end{align*}$$

as desired.

Answer 2

Hint: use the hint until it says "use the binomial theorem". Instead use $$ \binom{n}{k} \le \frac{{n^k }}{{k!}} $$ and the Taylor series of the exponential function.

Answer 3

You want to show $$\left(\frac mn\right)^m \sum_{k=0}^m{n\choose k}\leq e^m$$ But $$\left(\frac mn\right)^m \sum_{k=0}^m{n\choose k}= \sum_{k=0}^m\left(\frac mn\right)^m{n\choose k}\leq \sum_{k=0}^m\left(\frac mn\right)^k{n\choose k} \leq \sum_{k=0}^n\left(\frac mn\right)^k{n\choose k} =\left(1+\frac{m}{n}\right)^n$$ since $m\le n$, so $m/n\le 1$, and the last equality is the binomial theorem.

But for every $x\ge 0$, one has $(1+\frac xn)^n \leq e^x$, so $$(1+\frac{m}{n})^n\leq e^m$$ and we are done.