Combinatorial ProofDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/