Results 1 to 2 of 2

Math Help - Combination Proof - Need help understanding steps in answer

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    83

    Combination Proof - Need help understanding steps in answer

    Hey,

    I am working through some review questions for my mid term, and came across this problem:
    Prove:
     C(n , r) = C(n-1 , r -1) + C(n-1 , r )

    I tried the problem, and my semi-complete solution looks just like the answer in the back, but I only got so far. Here is the answer in the back (with notes of me asking what is going on, and why):

     LS = \frac {n!}{(n-3)!r!}

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

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

    *Above is how far I got, after this I have little understanding what is happening.*

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

    *Okay, so where did the r come from on top on the left fraction? as-well as the r on the bottom. The right fraction suddenly is multiplied by "(n-r)"...why?*

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

    *this step also doesn't make sense to me. How does the bottom of the left fraction become that? I realize they have a common denominator now, but I do not understand their multiplication. On either side.*

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

    *Do not understand the addition here, at all. A webpage explaining something similar may clear this up. Will be searching after I finish typing this post*

     = \frac {(n-1)!n}{(n-r)!r!}

    *this makes sense, they added the r and -r together to get 0, so just left with the n on top*

     = \frac {!n}{(n-r)!r!}

    *do not understand how the "(n-1)" disappears from the top here.*

     = \frac {!n}{(n-r)!r!}

    *This is how it is shown in the book. I assume the factorial still applies even when it is infront of the n. I understand this to be what C(n,r) looks like.

    Hopefully the point of this thread makes sense to you. I am asking questions about an answer in the back, that I do not understand, and am looking for help with.

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

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by Kakariki View Post
    Hey,

    I am working through some review questions for my mid term, and came across this problem:
    Prove:
     C(n , r) = C(n-1 , r -1) + C(n-1 , r )

    I tried the problem, and my semi-complete solution looks just like the answer in the back, but I only got so far. Here is the answer in the back (with notes of me asking what is going on, and why):

     LS = \frac {n!}{(n-3)!r!}

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

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

    *Above is how far I got, after this I have little understanding what is happening.*

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

    *Okay, so where did the r come from on top on the left fraction? as-well as the r on the bottom. The right fraction suddenly is multiplied by "(n-r)"...why?*


    Both fractions are multiplied by 1, which doesn't change them: the first one is multiplied by \frac{r}{r}=1 , and the second one by \frac{n-r}{n-r}=1...this is a

    pretty standard trick in many parts of mathematics.



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

    *this step also doesn't make sense to me. How does the bottom of the left fraction become that? I realize they have a common denominator now, but I do not understand their multiplication. On either side.*


    For any natural n>1\,,\,\,n(n-1)!=(n-1)!n=n! , so (r-1)!r=r! on the left fraction's denominator , and (n-r)(n-r-1)!=(n-r)! , on the right one's denominator.


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

    *Do not understand the addition here, at all. A webpage explaining something similar may clear this up. Will be searching after I finish typing this post*


    They just added the fractions and factored out (n-1)! in the numerator!


     = \frac {(n-1)!n}{(n-r)!r!}

    *this makes sense, they added the r and -r together to get 0, so just left with the n on top*

     = \frac {!n}{(n-r)!r!}

    *do not understand how the "(n-1)" disappears from the top here.*


    Read the second note in blue


     = \frac {!n}{(n-r)!r!}

    *This is how it is shown in the book. I assume the factorial still applies even when it is infront of the n. I understand this to be what C(n,r) looks like.


    The ! sign in front of a number is either a typographic error, or else some non-standard notation they explain somewhere in the book, or somebody was high when printing the book, but it definitely is not the same as the ! sign AFTER the number, which is the standard, correct way to write it.

    Tonio


    Hopefully the point of this thread makes sense to you. I am asking questions about an answer in the back, that I do not understand, and am looking for help with.

    - Thanks in advanced!
    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 11th 2011, 03:31 PM
  2. Replies: 1
    Last Post: March 10th 2011, 06:11 AM
  3. Replies: 2
    Last Post: June 19th 2010, 01:59 AM
  4. Replies: 2
    Last Post: March 2nd 2010, 07:18 AM
  5. [SOLVED] Is this answer and steps correct?
    Posted in the Algebra Forum
    Replies: 5
    Last Post: June 3rd 2009, 09:34 PM

Search Tags


/mathhelpforum @mathhelpforum