Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

Thanks in advance.

share|improve this question
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
add comment

3 Answers

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!}, $$


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

share|improve this answer
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
add comment

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

share|improve this answer
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
add comment

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

Gerhard "Ask Me About Rough Estimates" Paseman, 2013.05.17

share|improve this answer
By the way, I would like some context. If this was a homework problem, I expect you to credit MathOverflow in your writeup. If it wasn't, some acknowledgement would still be appreciated. Gerhard "Or Maybe A Gift Card" Paseman, 2013.05.17 –  Gerhard Paseman May 17 '13 at 16:51
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.