Results 1 to 3 of 3

Math Help - proof by induction

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    3

    proof by induction

    Hey just wondering if anyone could give me some help with this problem

    prove by induction that:

    \binom{2n}{n} \frac{4^n}{2\sqrt(n)}
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by pthomson75268 View Post
    Hey just wondering if anyone could give me some help with this problem

    prove by induction that:

    \binom{2n}{n} \frac{4^n}{2\sqrt(n)}
    Hi pthomson75268,

    sorry, this was posted in error.
    My work is below.
    Last edited by Archie Meade; February 17th 2010 at 08:13 AM. Reason: post hadn't been completed
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by pthomson75268 View Post
    Hey just wondering if anyone could give me some help with this problem

    prove by induction that:

    \binom{2n}{n} \frac{4^n}{2\sqrt(n)}
    Hi pthomson75268,

    If \binom{2n}{n}\ \ge\ \frac{4^n}{2\sqrt{n}}

    then this statement is used to try to prove if \binom{2(n+1)}{n+1}\ \ge\ \frac{4^{n+1}}{2\sqrt{n+1}}

    Proof

    \binom{2k+2}{k+1}=\frac{(2k+2)!}{[(2k+2)-(k+1)]!(k+1)!}=\frac{(2k+2)(2k+1)[(2k)!]}{(2k-k+1)!(k+1)!}

    =\frac{(2k+1)(2k+1)[(2k)!]}{(2k-k+1)(2k-k)!(k+1)k!}= \frac{(2k+2)(2k+1)}{k+1)(k+1)}\ \frac{(2k)!}{(2k-k)!k!}=\frac{(2k+2)(2k+1)}{(k+1)^2}\ \binom{2k}{k}

    We need to test if this is \ge\ \frac{4^{k+1}}{2\sqrt{k+1}}

    \frac{4^{k+1}}{2\sqrt{k+1}}=\frac{4^k(4\sqrt{k})}{  2\sqrt{k}\sqrt{k+1}}=\frac{4^k}{2\sqrt{k}}\ \left(\frac{4\sqrt{k}}{\sqrt{k+1}}\right)

    Therefore, if \frac{(2k+2)(2k+1)}{(k+1)^2}\ \ge\ \frac{4\sqrt{k}}{\sqrt{k+1}}

    then \binom{2(k+1)}{k+1}\ \ge\ \frac{4^{n+1}}{2\sqrt{k+1}} definately

    Hence, the question now is... is \frac{4k^2+6k+2}{(k+1)^2}\ \ge\ \frac{4\sqrt{k}\sqrt{k+1}}{k+1} ?

    \frac{4k^2+6k+2}{(k+1)^2}\ \ge\ \frac{4\sqrt{k}\sqrt{k+1}(k+1)}{(k+1)^2} ?

    4k^2+6k+2\ \ge\ 4\sqrt{k}\sqrt{k+1}(k+1) ?

    \left(4k^2+6k+2\right)^2\ \ge\ 16k(k+1)(k+1)^2 ?

    16k^4+48k^3+52k^2+24k+4\ \ge\ 16k^4+48k^3+48k^2+16k ?

    Yes,

    therefore, the trail of gunpowder has been put in place.
    You only need light the match by proving the inequality for the first value of n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction
    Posted in the Algebra Forum
    Replies: 13
    Last Post: January 31st 2011, 05:41 PM
  2. an induction proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 5th 2009, 02:31 PM
  3. proof by induction ...
    Posted in the Calculus Forum
    Replies: 2
    Last Post: August 8th 2009, 03:07 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum