Combination: Proof

**Khorne** · February 24th 2009, 01:56 AM

Hey all!

I have a question, which I've been pondering over for a few hours, and just can't seem to grasp it.

It goes:

(m+n)C(3) = (m)C(3) + (m)C(2)*(n)C(1) + (m)C(1)*(n)C(2) + (n)C(3)

I've tried simplify the LHS down to (m+n)(m+n-1)(m+n-2)/3! But this didn't help, and I've tried simplify, and canceling down the RHS too, but I always end up with a huge expansion (18 terms

).

Could anyone lend a helping hand? Or some insight into the problem?

Thanks!

**red_dog** · February 24th 2009, 06:59 AM

We have $(1+x)^{m+n}=(1+x)^m(1+x)^n$

The coefficient of $x^3$ in the LHS is $C_{m+n}^3$

The coefficient of $x^3$ in the RHS is $C_m^3+C_m^2C_n^1+C_m^1C_n^2+C_n^3$

But the coefficients are the same, so we have the equality.