Results 1 to 3 of 3

Thread: Proving an inequality with summations and binomial coefficients

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    12

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2010
    Posts
    12

    oh yeah

    Forgot to mention, both b and a are positive integers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by RespeckKnuckles View Post
    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.
    Last edited by melese; Sep 29th 2010 at 05:52 PM. Reason: pedantic, adding space
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Inequality with binomial coefficients
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Sep 8th 2011, 10:17 AM
  2. binomial coefficients
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: Jun 6th 2009, 01:23 AM
  3. Binomial coefficients?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 23rd 2009, 09:00 AM
  4. Binomial coefficients
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Feb 13th 2009, 12:22 PM
  5. Stats: proving an equality with summations
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Feb 2nd 2009, 09:41 AM

Search Tags


/mathhelpforum @mathhelpforum