Problem
COM-B2-M09-P005 Vandermonde's Identity
#5
★★☆☆☆ Level 2 of 5
Prove using generating functions that for nonnegative integers \(r,s,n\),
\[\sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n}.\]
Compare the coefficient of \(x^n\) in \((1+x)^r(1+x)^s\) in two ways.
On one hand, \((1+x)^r(1+x)^s=(1+x)^{r+s}\), so the coefficient of \(x^n\) is \(\binom{r+s}{n}\). On the other hand, to obtain \(x^n\), we may take \(x^k\) from the first factor and \(x^{n-k}\) from the second. This gives \(\sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k}\). The coefficients of the same polynomial are equal, so the identity is proved.
A standard application: proving an identity without algebraically expanding sums.