Results 1 to 5 of 5

Thread: 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 : $\displaystyle \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 $\displaystyle 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
    2,005
    Thanks
    747

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

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

    1. Show the base case $\displaystyle P_0$ is true:

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

    $\displaystyle 1\ge1$

    True.

    2. State the induction hypothesis $\displaystyle P_k$:

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

    Next, look at:

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

    and

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

    That is, see if $\displaystyle 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 :
    -> $\displaystyle (2k)!$ is $\displaystyle > (k!)^2$
    -> the left "big parenthesis" is > the right "big parenthesis"

    But what about the $\displaystyle 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; Jan 9th 2013 at 03: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
    2,005
    Thanks
    747

    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
    2,005
    Thanks
    747

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

    You should verify that:

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

    and

    $\displaystyle \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:

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

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

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

    $\displaystyle 4k+2\ge0$

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

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

    and then adding the result to $\displaystyle P_k$, we will obtain $\displaystyle 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: Jul 5th 2011, 10:51 AM
  2. Prove that g(x) greater than/equal to 0?
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 24th 2009, 02:23 AM
  3. Replies: 10
    Last Post: Mar 24th 2009, 11:11 PM
  4. Replies: 2
    Last Post: Mar 23rd 2009, 07:11 AM
  5. greater than, equal to or less than zero
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Sep 23rd 2008, 04:09 AM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum