# How to prove upper bound for partial sum of binomial coefficients

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!

## 1 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) by induction with respect to $$n$$. For $$m=1$$ we have $$f(m,n)=1+n For $$n=m$$ we have $$f(m,n)=2^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) 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.$$