Binomial Theorem Proof: (nC0)(mC0) + (nC1)(mC1) + ... + (nCm)(mCm) = (n+m C m)

[lifeonfire]

Homework Statement

To Prove:
(nC0)(mC0) + (nC1)(mC1) + ... + (nCm)(mCm) = (n+m C m)

where nC0 = n choose 0 and so on.

Homework Equations

The Attempt at a Solution

Tried expanding the whole thing using factorials - but didn't work. Any hints would be really welcome!

 

[fzero]

You should review proof by induction and then try to apply it here.

 

[lifeonfire]

Do I do induction on m?? So that would mean , that by assumption ...+(nCm)(mCm) = (n+m C m)...then to prove ...+(nCm+1)(m+1Cm+1) = (n+m+1 C m+1) ...correct?

 

[fzero]

Yes, that should work.