Proving N C R x M C R-r = (N+M) C R

[the4thamigo_uk]

Homework Statement

If (N,R) indicates number of combinations of R objects selected from set of N objects N >=r then prove :

R
E (N,r) x (M,R-r) = (N+M, R)
r=0

E specifies the usual capital sigma notion for a sum.

The Attempt at a Solution

Just don't know how to tackle this? Inductive proof may be possible but we have three variables N, M and R, so its non trivial?

Any clues?

 

[I like Serena]

Hola the4thamigo_uk!

Suppose we have 2 bins with respectively N balls and M balls, and we take a total of R balls from both bins.
What are the possibilities for the number of balls to take from the first bin?
And how do they combine with the balls from the second bin?

 

[the4thamigo_uk]

Yes I understand the situation and the combinatoric proof, but how would I formally prove it?

 

[I like Serena]

Hmm, let's see...

Suppose we take generic variables a and b, then:
(a+b)^N+M = (a+b)^N (a+b)^M

Working this out you get:
(... + C(N+M,R) a^R b^N+M-R + ... ) = (C(N,0)a⁰ b^N + C(N,1)a¹ b^N-1 + ...) (C(M,0)a⁰ b^M + C(M,1)a¹ b^M-1 + ...)

To get the specific term on the left side, you need to combine the terms on the right side in such a way that corresponds exactly to your equation.
So the equation must hold true.