# Thread: Proving an inequality with summations and binomial coefficients

1. ## Proving an inequality with summations and binomial coefficients

I just can't figure this out. Can someone point me in the right direction? I need to prove, that for all b >= a:
$\displaystyle \sum_{i=0}^{a} \binom{b}{i} \le (\frac{eb}{a})^a$

Two hints I was given were (first one is possible because b > a):
$\displaystyle \sum_{i=0}^a \binom{b}{i} \le \sum_{i=0}^a (\frac{b}{a})^{(a-i)} \binom{b}{i}$
and
$\displaystyle (1 + \frac{1}{x})^x \le e$

I've tried everything I could think of...using the binomial formula, expanding the first hint, etc. Always seem to hit dead ends.

2. ## oh yeah

Forgot to mention, both b and a are positive integers.

3. Originally Posted by RespeckKnuckles
I just can't figure this out. Can someone point me in the right direction? I need to prove, that for all b >= a:
$\displaystyle \sum_{i=0}^{a} \binom{b}{i} \le (\frac{eb}{a})^a$

Two hints I was given were (first one is possible because b > a):
$\displaystyle \sum_{i=0}^a \binom{b}{i} \le \sum_{i=0}^a (\frac{b}{a})^{(a-i)} \binom{b}{i}$
and
$\displaystyle (1 + \frac{1}{x})^x \le e$

I've tried everything I could think of...using the binomial formula, expanding the first hint, etc. Always seem to hit dead ends.
The first hint implies that it's enough to show that (*)$\displaystyle \sum_{i=0}^{a}(\frac{b}{a})^{a-i}\binom{b}{i}\le(\frac{eb}{a})^a$.

By direct calculation, $\displaystyle \displaystyle{\sum_{i=0}^{a}\left(\frac{b}{a}\righ t)^{a-i}\binom{b}{i}}$ $\displaystyle =\sum_{i=0}^{a}(\frac{b}{a})^a(\frac{b}{a})^{-i}\binom{b}{i}=\sum_{i=0}^{a}(\frac{b}{a})^a(\frac {a}{b})^i\binom{b}{i}=(\frac{b}{a})^a\left[\sum_{i=0}^{a}(\frac{a}{b})^i\binom{b}{i}\right]$ $\displaystyle \displaystyle\le\left(\frac{b}{a}\right)^a\left[\sum_{i=0}^{b}\left(\frac{a}{b}\right)^i\binom{b}{ i}\right]$ , where the last inequality holds because $\displaystyle b\ge a$. For convenience we refer only to the sum inside the brackets.

Now it follows by the Binomial Theorem that $\displaystyle \sum_{i=0}^{b}(\frac{a}{b})^i\binom{b}{i}=(1+\frac {a}{b})^b=(1+\frac{1}{b/a})^b=\left[(1+\frac{1}{b/a})^{b/a}\right]^a\le e^a$, where for the last inequality I applied the second hint.
Therefore, $\displaystyle \displaystyle\left(\frac{b}{a}\right)^a\left[\sum_{i=0}^{b}\left(\frac{a}{b}\right)^i\binom{b}{ i}\right]\le\left(\frac{b}{a}\right)^ae^a=\left(\frac{be}{a }\right)^a$ and from (*) the result follows.