Results 1 to 5 of 5

Math Help - Combinations Proof

  1. #1
    Junior Member
    Joined
    Jun 2008
    Posts
    27

    Combinations Proof

    Ok, this is what I need to do:

    "Prove that for any n and r where 0 <= r <= n,
    C(n,2) = C(r,2) + C(n-r,2) + r(n-r)"

    I can plug in numbers and see that this seems to hold true. But I am not sure how to prove this for any n and r that meets the condition.

    As far as an actual proof goes, I don't even know how to approach this. Can anyone give me a suggestion or poke me in the right direction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Just go straight by definition:
    C(n,2) = C(r,2) + C(n-r,2) + r(n-r)

    \text{LHS} = \frac{n!}{2!(n-2)!} = \frac{n{\color{blue}(n-1)(n-2)!}}{2!(n-2)!} =  \frac{n(n-1)}{2}

    (Notice how I split up the factorial in the numerator to get rid of the one in the denominator)

    Now you have to show that the right hand side simplifies to the same thing. You know it does. It's just a matter of going through all the algebra to prove it.

    \text{RHS} = \frac{r!}{2!(r-2)!} + \frac{(n-r)!}{2!(n-r-2)!} + r(n-r)
    \text{RHS} = \frac{r{\color{blue}(r-1)(r-2)!}}{2(r-2)!} + \frac{(n-r){\color{blue}(n-r-1)(n-r-2)!}}{2(n-r-2)!} + nr - r^{2}
    etc. etc.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2008
    Posts
    27
    Hmm, I see...
    Ok, I'm going to play with this one for a while, but I think I understand what you're talking about!
    Thanks o_O!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by mander View Post
    Ok, this is what I need to do:

    "Prove that for any n and r where 0 <= r <= n,
    C(n,2) = C(r,2) + C(n-r,2) + r(n-r)"

    I can plug in numbers and see that this seems to hold true. But I am not sure how to prove this for any n and r that meets the condition.

    As far as an actual proof goes, I don't even know how to approach this. Can anyone give me a suggestion or poke me in the right direction?
    Such problems can also be done by double counting.

    LHS says you want to count the number of ways to choose 2 balls out n balls in a box.

    Lets count it differently now,
    Now since 0 <= r <= n, we can break that collection into two boxes, one containing r balls(call it "r-box") and the other containing n-r balls(call it "(n-r)-box").

    Now choosing 2 balls from this arrangement breaks down into the following three choices:

    1) Both balls are from the r-box => There are C(r,2) ways to choose

    2) Both balls are from the (n-r)-box => There are C(n-r,2) ways to choose

    3) One from each of the boxes => There are C(r,1)*C(n-r,1) ways to choose

    Thus effectively total number of ways to choose 2 balls out of n balls in this scenario is
    C(r,2)+C(n-r,2)+C(r,1)C(n-r,1) = C(r,2)+C(n-r,2)+r(n-r)

    Since we are counting the same setting in two different ways, they must be equal. Thus

    C(n,2) = C(r,2) + C(n-r,2) + r(n-r)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2008
    Posts
    27
    Hi Isomorphism,
    Thanks for your explanation too! I find it a little confusing but I do understand it much better now (I think and hope ). Thanks for your help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof regarding combinations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 18th 2010, 02:44 PM
  2. Proof with Combinations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 20th 2009, 08:04 AM
  3. combinations proof by induction?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 18th 2009, 12:03 AM
  4. combinations proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 4th 2009, 06:34 AM
  5. [SOLVED] Discrete Math Proof: Combinations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 24th 2009, 06:46 PM

Search Tags


/mathhelpforum @mathhelpforum