# How to prove?

1. Sep 26, 2011

### the4thamigo_uk

1. The problem statement, all variables and given/known data

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.

3. The attempt at a solution

Just dont 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?

2. Sep 26, 2011

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

3. Sep 26, 2011

### the4thamigo_uk

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

4. Sep 26, 2011

### 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) aR bN+M-R + ... ) = (C(N,0)a0 bN + C(N,1)a1 bN-1 + ...) (C(M,0)a0 bM + C(M,1)a1 bM-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.