# how to proof this Stirling related equation

here is what I need to proof, have no idea were to start. I know there is some connection with the Stirling theorem.

$$\sum_{i=0}^{d}\binom{m}{i} \leq \left ( \frac{em}{d} \right )^{d}$$

I tried to open the sum and start from the right side of the equation but nothing achieved.

-
the left hand side is infinite, so the inequality is obviously false. – Carlo Beenakker May 17 '13 at 10:27
I am a bit slow, why is the left hand side infinite? – András Bátkai May 17 '13 at 12:46
sorry, I misunderstood the left and right hand side both as fractions, my mistake – Carlo Beenakker May 17 '13 at 13:33

First, observe that

$${m!\over(m-i)!} \le m^i$$

for $0\le i\le m$. (The two sides are equal for $i=0$ and $1$. Otherwise the inequality is strict: The left hand side is a product of $i$ positive integers, none greater than $m$.) It follows that, for $0\le i \le d \le m$, we have

$$\left({d\over m}\right)^d{m\choose i}= {d^i\over i!}\left({d\over m}\right)^{d-i}{m!\over m^i(m-i)!} \le {d^i\over i!},$$

hence

$$\left({d\over m}\right)^d\sum_{i=0}^d {m\choose i} \le \sum_{i=0}^d {d^i\over i!} \lt \sum_{i=0}^\infty {d^i\over i!} =e^d.$$

The desired inequality follows.

(Note: The OP did not explicitly assume that $d\le m$, but it's reasonable to assume he or she meant to. In particular, if $d\gt em$, the OP's inequality is false.)

-
Nice avoidance of Stirling. To avoid confusion with misuse of the empty product, I recommend using the first line for $1 \leq i \leq d,$ and then assert the second line for $0 \leq i \leq d.$ Gerhard "Don't Want Greater Than One" Paseman, 2013.05.17 – Gerhard Paseman May 17 '13 at 23:09
@Gerhard, good point. I rewrote things to make them hopefully more clear. – Barry Cipra May 18 '13 at 14:15

Assume that $d\le m$. Certainly we have $\binom{m}{d}\le (\frac{em}{d})^d$. From this one can deduce $$f(m,d)=\sum_{i=0}^d\binom{m}{i} \le \frac{1-r^{d+1}}{1-r}\binom{m}{d}\le \frac{1-r^{d+1}}{1-r}\left(\frac{em}{d}\right)^d$$ for $r=\frac{d}{m-d+1},$ see Sum of 'the first k' binomial coefficients for fixed n . However, this is not good enough. One could use then a better upper bound for $\binom{m}{d}$ in the last inequality.

EDIT: I just saw that Gerhard Pasemann has a better solution with case distinction $3d< m$ and $3d \ge m$.

-
You might fare better if you consider separately the cases 2d < m and 2d > m. Gerhard "Ask Me About Binomial Sums" Paseman, 2013.05.17 – Gerhard Paseman May 17 '13 at 15:23

Here is a simple approach. The left hand side (for fixed $m$) is always at most $2^m$, so when is the right hand side bigger than $2^m$? Rewriting $k = \frac{m}{d},$ this is the same as asking for which $k$ is $ek > 2^k$? By inspection or calculus, one has it true for $1 \leq k \leq 3$, so when $d$ is between $m/3$ and $m$, the inequality holds. For $d \lt m/3$, the right hand side (by Stirling) is larger than $\sqrt{2\pi d}\binom{m}{d}$, which in turn is larger than twice the largest summand on the left hand side. As has been noted elsewhere, this is an upper bound for the sum when $3d \leq m,$ showing the inequality holds for small $d$.