Combinatorial Proof

Date: 6/13/96 at 17:29:38
From: Anonymous
Subject: combinatorial proof

Could you please prove the following combinatorial proof?

  r
-----|
 \
  >   nCk*mC(r-k)=(n+m)Cr
 /
-----|
 k=0

   thanks,
     Mike

Date: 6/14/96 at 5:29:51
From: Doctor Anthony
Subject: Re: combinatorial proof

This is proved by considering the following identity:

 (1+x)^n*(1+x)^m = (1+x)^(n+m)

If you expand both brackets on the left hand side by the binomial 
theorem and pick out the products that give the term in x^r, then the 
sum of these coefficients will equal the coefficient of x^r on the 
right hand side.  This we know is (n+m)Cr.  

For example nC0*mCr + nC1*mC(r-1) + ... will 
be the coefficients found by taking 1 from the first bracket and the 
coefficient of x^r from the second bracket, plus the coefficient 
of x from the first bracket and the coefficient of x^(r-1) from 
the second bracket, and so on and so on.

-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/