Prove upper bound for partial sum of binomial coefficients

binomial-coefficientscombinatoricsinequality

I just come across this inequality for the upper bound of partial sum of binomial coefficients, that is
\begin{array}
$\sum_{k=0}^{m}\binom{n}{k}\leq (\frac{en}{m})^{m},
\end{array}
I have trying to prove it but not having much success. I have used the stirling forluma $n!=\sqrt{2\pi}n^{n+1/2}e^{^{-n+r(n)}}$, where $r(n)\in (\frac{1}{12n+1}, \frac{1}{12n})$, thus I get $\frac{1}{k!}\leq (\frac{e}{k})^{k}$, and $\binom{n}{m}\leq (\frac{en}{m})^{m}$ for all intergers $m \in [1, n]$, which is just one item case, but that still has a big gap with $\sum_{k=0}^{m}\binom{n}{k}\leq (\frac{en}{m})^{m}$.
I just don't how to further expand the case the partial sum case? Any hints or insights would be helpful! Thanks!

Best Answer

For each $1\le m\le n$ put $$f(m,n)=\sum_{k=0}^{m}\binom{n}{k}\mbox{ and }g(m,n)=\left (\frac{en}{m}\right)^{m}.$$ We prove that $f(m,n)<g(m,n) $ by induction with respect to $n$. For $m=1$ we have $$f(m,n)=1+n<en=g(m,n).$$ For $n=m$ we have $f(m,n)=2^n<e^n$. In particular, we have the base of the induction. Using that $${n\choose k}+{n\choose k+1}={n+1\choose k+1}$$ for each $0\le k\le n-1$, we have that $$f(m+1, n+1)=f(m,n)+f(m+1,n)$$ for each $1\le m\le n-1$. By the induction hypothesis, in order to show that $$f(m+1,n+1)<g(m+1,n+1)$$ it suffices to show that $$g(m+1, n+1)\ge g(m,n)+g(m+1,n).$$ Check this inequality

$$g(m+1, n+1)\ge g(m,n)+g(m+1,n)$$

$$\left(\frac{e(n+1)}{m+1}\right)^{m+1}\ge \left (\frac{en}{m}\right)^{m}+\left (\frac{en}{m+1}\right)^{m+1}$$

$$e\left(\frac{(n+1)}{m+1}\right)^{m+1}\ge \left (\frac{n}{m}\right)^{m}+e\left (\frac{n}{m+1}\right)^{m+1}$$

Since $$\left (\frac{(n+1)}{m+1}\right)^{m+1}=\left (\frac{n}{m+1}+\frac{1}{m+1}\right)^{m+1}\ge \left (\frac{n}{m+1}\right)^{m+1}+(m+1) \left(\frac{n}{m+1}\right)^{m}\frac{1}{m+1},$$

it suffices to show that

$$e\left (\frac{n}{m+1}\right)^{m}\ge \left (\frac{n}{m}\right)^{m}$$

$$e\ge \left (\frac{m+1}{m}\right)^{m}$$

$$e^{\frac 1m}\ge \frac{m+1}{m}$$

Which is true, because

$$e^{\frac 1m}=1+{\frac 1m}+{\frac 1{2m^2}}+\dots.$$

Related Question