Results 1 to 5 of 5

Math Help - Binomial proof

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    2

    Question Binomial proof

    I have to prove that
    n+1 choose k = n choose k + n choose k-1

    Where on earth do I start? Any help much appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by eliz1906 View Post
    I have to prove that
    n+1 choose k = n choose k + n choose k-1

    Where on earth do I start? Any help much appreciated!
    Hi Eliz1906,

    If we work from the right...

    \binom{n+1}{k}=\frac{(n+1)!}{(n+1-k)!k!}

    \binom{n}{k}+\binom{n}{k-1}=\frac{n!}{(n-k)!k!}+\frac{n!}{(n+1-k)!(k-1)!}

    We express the sum with the same denominators as \binom{n+1}{k}

    \frac{n!}{(n-k)!k!}=\frac{n!}{\frac{(n+1-k)!}{n+1-k}k!}

    \frac{n!}{(n+1-k)!(k-1)!}=\frac{n!}{(n+1-k)!\frac{k!}{k}}

    Therefore

    \frac{n!(n+1-k)}{(n+1-k)!k!}+\frac{n!k}{(n+1-k)!k!}=\frac{n!(n-k+1-k)}{(n+1-k)!k!}

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

    =\binom{n+1}{k}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    644
    Hello, eliz1906!

    It takes only algebra . . . a lot of it!


    Prove: . {n+1\choose k} \;=\;{n \choose k} + {n\choose k-1  }

    The right side is: . \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!}


    Get a common denominator:

    \frac{n!}{k!(n-k)!}\cdot{\color{blue}\frac{(k-1)!(n-k+1)!}{(k-1)!(n-k+1)!}} \;+\; \frac{n!}{(k-1)!(n-k+1)!}\cdot{\color{blue}\frac{k!(n-k)!}{k!(n-k)!}}

    . . . . = \;\frac{n!(k-1)!(n-k+1)! \;+\; n!k!(n-k)!}{k!(k-1)!(n-k)!(n-k+1)!}


    Factor: . \frac{n!(k-1)!(n-k)!\,\bigg[(n-k+1) + k\bigg]}{k! (k-1)! (n-k)!(n-k+1)!}

    Reduce: . \frac{n!{\color{red}\rlap{///////}}(k-1)!{\color{green}\rlap{///////}}(n-k)!\,\bigg[(n-k+1) + k\bigg]}{k! {\color{red}\rlap{///////}}(k-1)! {\color{green}\rlap{///////}}(n-k)!(n-k+1)!}

    . . . . . . =\; \frac{n!(n+1)}{k!(n+1-k)!}

    . . . . . . =\;\frac{(n+1)!}{k!(n+1-k)!}

    . . . . . . =\quad {n+1\choose k}



    Edit: Ah, Archie beat me to it!
    . . . .But I'm not deleting all this work . . . So there!
    .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2010
    Posts
    2

    Red face

    Thank you SOOO much.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Sorry Soroban!

    I was quick out of the blocks there!
    I'm always glad to see you join in.

    Your post was beautifully illustrated, I must say.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof using Binomial Theorem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 29th 2011, 04:22 PM
  2. Binomial Proof
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: October 12th 2010, 06:50 AM
  3. Binomial proof?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 15th 2009, 12:26 PM
  4. Binomial Number proof
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 20th 2009, 09:39 AM
  5. Binomial distribution proof of mean
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: December 6th 2007, 09:48 AM

Search Tags


/mathhelpforum @mathhelpforum