$\sum_{i=1}^{k} \binom{n}{i} \le (\frac{en}{k})^k$

Question

prove $$\sum_{i=1}^{k} \binom{n}{i} \le (\frac{en}{k})^k$$

this inequality comes after:

1. show that for every $1\le k\le n$ and $0 \lt x \lt 1 $ $$ \binom{n}{k}x^k \le (1+x)^n \le e^{xn}$$

2. show that$$ \binom {n}{k} \le (\frac{en}{k})^k$$

I solved the first two parts, and now to solve the last part I used $x = \frac{k}{n}$

so I got :

$$(1+x)^n = (1+\frac{k}{n})^n = \sum_{i=0}^n\binom{n}{i}(\frac{k}{n})^i \le e^{xn} = e^k$$

multiply both sides of the equation by $(\frac{n}{k})^k$ to get: $$ \sum_{i=0}^n\binom{n}{i}(\frac{n}{k})^{k-i} \le (\frac{en}{k})^k$$

How can I conclude now the final step?

$$\sum_{i=1}^{k} \binom{n}{i} \le \sum_{i=0}^n\binom{n}{i}(\frac{n}{k})^{k-i}$$

Answer 1

Note that $$ \binom{n}{i} \geq \left( \frac{n}{i} \right)^i . $$ You get $$ \sum_{i=1}^k\left( \frac{n}{i} \right)^i\leq \sum_{i=1}^k\binom{n}{i} \leq \left( \frac{en}{k} \right)^k . $$ Since $$ \sum_{i=1}^k\left( \frac{n}{i} \right)^i\leq k \left( \frac{n}{k} \right)^k $$ and obviously $$ k \left( \frac{n}{k} \right)^k \leq e^k \left( \frac{n}{k} \right)^k $$ the inequality holds true.