Results 1 to 3 of 3

Math Help - 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:
    <br />
\sum_{i=0}^{a} \binom{b}{i} \le (\frac{eb}{a})^a<br />

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

    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:
    <br />
\sum_{i=0}^{a} \binom{b}{i} \le (\frac{eb}{a})^a<br />

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

    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 (*) \sum_{i=0}^{a}(\frac{b}{a})^{a-i}\binom{b}{i}\le(\frac{eb}{a})^a.

    By direct calculation, \displaystyle{\sum_{i=0}^{a}\left(\frac{b}{a}\righ  t)^{a-i}\binom{b}{i}} =\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\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 b\ge a. For convenience we refer only to the sum inside the brackets.

    Now it follows by the Binomial Theorem that \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\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; September 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: September 8th 2011, 10:17 AM
  2. binomial coefficients
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: June 6th 2009, 01:23 AM
  3. Binomial coefficients?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 23rd 2009, 09:00 AM
  4. Binomial coefficients
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 13th 2009, 12:22 PM
  5. Stats: proving an equality with summations
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 2nd 2009, 09:41 AM

Search Tags


/mathhelpforum @mathhelpforum