Results 1 to 5 of 5

Math Help - n Choose k Formula

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    30

    n Choose k Formula

    Prove by induction on n that "n choose k" = (n!) / k!(n-k)!

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

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,649
    Thanks
    1597
    Awards
    1
    Quote Originally Posted by meggnog View Post
    Prove by induction on n that "n choose k" = (n!) / k!(n-k)!
    Why in the world do you not learn to post in symbols? You can use LaTeX tags.
    [tex]\binom{N}{K}=\frac{N!}{K!(N-K)!}[/tex] gives \binom{N}{K}=\frac{N!}{K!(N-K)!}.
    We can then read your question.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member mohammadfawaz's Avatar
    Joined
    Feb 2010
    From
    Lebanon - Beirut
    Posts
    100
    This formula was derived from the definition of \binom{N}{K}. How are you planning to prove it by induction? you can go to an example and prove that choosing a set of K elements from a large set of N elements can occur in that number of ways but I'm not sure about induction.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    here is an outline that i think will work:

    Step1: Show its true for ^nC_1

    Step2: Show that if it is true for ^nC_k then it must be true for ^{n}C_{k+1}






    Step 1: Show ^nC_1 is correct
    This is trivial so I'll leave it to you. (substitute k=1 in your formula, and see that you get n as the answer)


    Step 2
    Find the relationship between ^nC_k and ^nC_{k+1} and show your proposition has this property.

    Think: How can i choose (k+1) from n?
    i can choose (k) from n, then choose 1 more from the remainder. There will be duplicates in this method that must be adjusted for. Each combination is duplicated exactly k+1 times. (Corresponding to the (k+1) positions that the "1 from the remainder" could take in the combination).


    So:
    ^nC_{k+1} =  ^nC_{k} * \frac{^{n-k}C_{1}}{k+1}

    The final adjustment of (k+1) on the right hand side is to remove duplicate combinations. Every combination appears (k+1) times, corresponding to the (k+1) positions that the "1 more" selected can take. I've done it with n=4 as an example below:

    Aside: Duplicate combinations
    Lets find ^{5}C_3

    If Yes = Selected and No = Not slected, there are the usual 10 combinations
    YYYNN
    YYNYN
    ....


    Now, lets get all the combinations by choosing 2 from 5 (Y), and 1 more from the remainder (y). two items are not selected (N).
    if i use this algorithm, i can choose the "first 3" exactly 3 ways
    YYyNN
    YyYNN
    yYYNN

    all these are the same combination (first 3 selected).

    You can repeat this for all other ways of getting 5C3 if you like, and every combination will appear 3 times in the same way. This generalises to (k+1) which gives the adjustment in the formula below
    /Aside




    Now, wee need to show that this relationship holds for your formula.
    ^nC_{k+1} =  ^nC_{k} * \frac{^{n-k}C_{1}}{k+1}

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

    This is immediately obvious from the properties of the factorial function.
    ie,
    (x+1)! = (x+1)x!
    \frac{(x)!}{x} = (x-1)!
    Last edited by SpringFan25; June 12th 2010 at 11:59 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by meggnog View Post
    Prove by induction on n that "n choose k" = (n!) / k!(n-k)!

    Thanks in advance!
    If it was not clear (!!) that choosing k from n is \binom{n}{k}
    and there was a suspicion that the formula was valid (!!!)

    then "Proof by Induction" can verify it,
    though surely it's simpler to realise that \binom{n}{k}=\frac{^nP_k}{k!}

    P(k)

    Choose k from n is \binom{n}{k}=\frac{n!}{(n-k)!k!}

    P(k+1)

    Choose k+1 from n is \binom{n}{k+1}=\frac{n!}{(n-[k+1])!(k+1)!}=\frac{n!}{(n-k-1)!(k+1)!}

    Proof

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

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

    Is this the number of ways to choose k+1 from n?

    To have an extra element in the selection, there are n-k to choose from.
    Any of those n-k elements can join the original k elements to form a selection of k+1.
    However, this new selection, having k+1 terms now, has k+1 ways to arrive at it, since any of k+1 new elements can have formed it from an original selection of k elements.

    Hence, the result obtained is correct.
    Finally test for k=1

    \frac{n-1}{2}\ \binom{n}{1}=\frac{n(n-1)}{2}

    \binom{n}{2}=\frac{n!}{(n-2)!2!}=\frac{n(n-1)(n-2!}{(n-2)!2}=\frac{n(n-1)}{2}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. n choose k
    Posted in the Statistics Forum
    Replies: 3
    Last Post: May 9th 2011, 01:17 PM
  2. how to choose
    Posted in the Statistics Forum
    Replies: 1
    Last Post: November 23rd 2010, 03:05 AM
  3. not sure which on to choose
    Posted in the Statistics Forum
    Replies: 8
    Last Post: June 9th 2008, 03:02 AM
  4. Replies: 1
    Last Post: March 19th 2008, 05:07 PM
  5. Choose from set
    Posted in the Statistics Forum
    Replies: 9
    Last Post: February 27th 2007, 09:19 PM

Search Tags


/mathhelpforum @mathhelpforum