Results 1 to 5 of 5

Math Help - Prove that 2n choose n is greater than or equal to ...

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    Montréal
    Posts
    14

    Prove that 2n choose n is greater than or equal to ...

    Our teacher asked this question in a homework :

    Prove : \binom{2n}{n} \ge \frac{4^{n}}{2n+1}

    I found these pages which gave me some clues :
    number theory - prove that $(2n)!/(n!)^2$ is even if $n$ is a positive integer - Mathematics
    Prove that 2n choose n is less than or equal to 4^n? - Yahoo! Answers

    However, I can't figure that out ! According to the 2nd page, if the right member was only 4^n, then the left member would be less than or equal to the right member.

    I just don't know what to do.

    You help would be appreciated.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Prove that 2n choose n is greater than or equal to ...

    I would use induction here. I will assume n\in\mathbb{N}_0

    1. Show the base case P_0 is true:

    {2\cdot0 \choose 0}\ge\frac{4^0}{2\cdot0+1}

    1\ge1

    True.

    2. State the induction hypothesis P_k:

    {2k \choose k}\ge\frac{4^k}{2k+1}

    Next, look at:

    {2(k+1) \choose k+1}-{2k \choose k}

    and

    \frac{4^{k+1}}{2(k+1)+1}-\frac{4^k}{2k+1}

    That is, see if P_{k+1}-P_k gives you a true inequality.

    What do you find?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2012
    From
    Montréal
    Posts
    14

    Re: Prove that 2n choose n is greater than or equal to ...

    The PDF file is what I got... but I'm not too sure how to compare left with right...

    I PROBABLY MADE ALGEBRAIC ERRORS !

    I know that :
    -> (2k)! is > (k!)^2
    -> the left "big parenthesis" is > the right "big parenthesis"

    But what about the 4^k ?!

    I'm surely this is much simpler than I think, but my brain's kind of burnt right now !

    Thanks !

    The PDF is in French, but I wrote English translation in red.
    Attached Files Attached Files
    Last edited by NZAU1984; January 9th 2013 at 04:39 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Prove that 2n choose n is greater than or equal to ...

    That is essentially the same technique I have in mind, but I can get you there much more simply. Unfortunately, I don't have the time at the moment. I will be glad to elaborate more in a few hours. If you compute the differences I suggest, it should all become clear.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Prove that 2n choose n is greater than or equal to ...

    You should verify that:

    {2(k+1) \choose k+1}-{2k \choose k}=\frac{3k+1}{k+1}{2k \choose k}

    and

    \frac{4^{k+1}}{2(k+1)+1}-\frac{4^k}{2k+1}=\frac{6k+1}{2k+3}\cdot\frac{4^k}{  2k+1}

    So, next, let's verify:

    \frac{3k+1}{k+1}\ge\frac{6k+1}{2k+3}

    (3k+1)(2k+3)\ge(6k+1)(k+1)

    6k^2+11k+3\ge6k^2+7k+1

    4k+2\ge0

    This is obviously true for k\in\mathbb{N}_0. So, multiplying the induction hypothesis P_k by:

    \frac{3k+1}{k+1}\ge\frac{6k+1}{2k+3}

    and then adding the result to P_k, we will obtain P_{k+1}, thereby completing the proof by induction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: July 5th 2011, 11:51 AM
  2. Prove that g(x) greater than/equal to 0?
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 24th 2009, 03:23 AM
  3. Replies: 10
    Last Post: March 25th 2009, 12:11 AM
  4. Replies: 2
    Last Post: March 23rd 2009, 08:11 AM
  5. greater than, equal to or less than zero
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 23rd 2008, 05:09 AM

Search Tags


/mathhelpforum @mathhelpforum