2
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.$$

$\endgroup$

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.