# Combination: Proof

• Feb 24th 2009, 01:56 AM
Khorne
Combination: Proof
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 (Worried)).

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

Thanks!
• Feb 24th 2009, 06:59 AM
red_dog
We have \$\displaystyle (1+x)^{m+n}=(1+x)^m(1+x)^n\$

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

The coefficient of \$\displaystyle x^3\$ in the RHS is \$\displaystyle 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.
• Feb 24th 2009, 11:58 AM
Khorne
Hello, and thank you.

However, could you just clarify the first line? I don't comprehend how you structure? or deduced it.
• Feb 24th 2009, 12:16 PM
Plato
Quote:

Originally Posted by Khorne
could you just clarify the first line? I don't comprehend how you structure? or deduced it.

You do know the basic laws of exponents.
• Feb 24th 2009, 06:59 PM
Khorne
Indeed, but not with this type of proof setting.