Results 1 to 5 of 5

Math Help - Binomial coefficient proof - where have I gone wrong in my working?

  1. #1
    Junior Member
    Joined
    Aug 2009
    From
    Brisbane, Australia
    Posts
    31

    Binomial coefficient proof - where have I gone wrong in my working?

    Hi all,

    I have been given the definition for the binomial coefficient as:

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

    (NOTE: I have written it as (n,k) because I'm not sure how to format it properly using Latex like it is seen in the textbook, with the n above the k. If anyone knows how to do this please let me know).

    Now, I am asked to prove that (n+1, k) = (n, k-1) + (n,k).

    Let S = n(n-1)...(n-k+1), then (n, k-1) = \frac{S}{(k-1)!} = \frac{kS}{k!} .
    Also, (n,k) = \frac{S}{k!}

    Adding them together gives: \frac{(k+1)S}{k!} .

    Now, (n+1,k) = \frac{(n+1)n...(n-k+2)}{k!}

    So to prove that (n+1, k) = (n, k-1) + (n,k) I need to show:

    (k+1)[n(n-1)...(n-k+1)] = (n+1)n...(n-k+2)

    At this point I know I have done something wrong, because I tried it out with real values (say n=6 and k=3), and they don't match:

    4(6 \cdot 5 \cdot 4) \neq (7 \cdot 6 \cdot 5)

    Can anyone help?

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    715
    Thanks
    2
    I couldn't follow your argument. Instead, start with:

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

    And take this over a common denominator.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2011
    From
    Bjelovar, Croatia
    Posts
    16
    Thanks
    1
    Btw! For  {n\choose k} you can write {n \choose k}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,962
    Thanks
    1784
    Awards
    1
    Quote Originally Posted by mrfour44 View Post
    Btw! For  {n\choose k} you can write {n \choose k}.
    Alternately, [tex]\binom{N}{k}[/tex] gives  \binom{N}{k}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2009
    From
    Brisbane, Australia
    Posts
    31
    Quote Originally Posted by TheCoffeeMachine View Post
    I couldn't follow your argument. Instead, start with:

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

    And take this over a common denominator.
    Thanks for that, I managed to solve it using the method you have specified, but I am still not sure why my original method does not work. I have gone over it a few times and still can't see the error in my reasoning. Also, can you tell me where you couldn't follow my working, as hopefully I can clarify/fix it up to make it more understandable.

    cheers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. binomial coefficient proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 17th 2010, 09:42 PM
  2. Binomial Coefficient Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 19th 2010, 06:13 PM
  3. Proof for an alternative binomial coefficient
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 22nd 2009, 11:04 AM
  4. Something wrong with my working.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 14th 2009, 03:55 AM
  5. Binomial Coefficient proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 27th 2008, 07:32 PM

Search Tags


/mathhelpforum @mathhelpforum