# Thread: Combinations Proof

1. ## 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?

2. 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.

3. 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!

4. Originally Posted by mander
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)

5. 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!