1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ the left hand side is infinite, so the inequality is obviously false. $\endgroup$ May 17, 2013 at 10:27
  • 2
    $\begingroup$ I am a bit slow, why is the left hand side infinite? $\endgroup$ May 17, 2013 at 12:46
  • $\begingroup$ sorry, I misunderstood the left and right hand side both as fractions, my mistake $\endgroup$ May 17, 2013 at 13:33

3 Answers 3

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ May 17, 2013 at 23:09
  • $\begingroup$ @Gerhard, good point. I rewrote things to make them hopefully more clear. $\endgroup$ May 18, 2013 at 14:15
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ May 17, 2013 at 15:23
1
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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 $\endgroup$ May 17, 2013 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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