Proof Vandermonde's identity using generating function

Question

Proof Vandermonde's identity using generating function $$\binom{m+n}{r}=\sum_{k=0}^r\binom{m}{r-k}\binom{n}{k}$$

$\binom{m+n}{r}$ is the coefficient of $x^r$ in $(1+x)^{m+n}$. Then I try, \begin{align} (1+x)^{m+n}&=(1+x)^m(1+x)^n\\ [x^r]\left(\sum_{k=0}^{m+n}\binom{m+n}{k}x^k\right)&=[x^r]\left(\sum_{k=0}^{m}\binom{m}{k}x^k\sum_{k=0}^{n}\binom{n}{k}x^k\right) \end{align} Now I lost. How to establish the identity$?$ any help will be appreciated.

Answer 1

Try putting the binomial coefficients in \begin{eqnarray*} (1+x)^{m+n}&=&(1+x)^m(1+x)^n\\ [x^r]\left(\sum_{k=0}^{m+n} \color{red}{\binom{m+n}{k}} x^k\right)&=&[x^r]\left(\sum_{k=0}^{m} \color{red}{\binom{m}{k}} x^k\sum_{k=0}^{n} \color{red}{\binom{n}{k}} x^k\right) \\ \binom{m+n}{r}&=&[x^r]\left(\sum_{i=0}^{m} \binom{m}{i} x^i\right) \left(\sum_{j=0}^{n} \binom{n}{j} x^j\right). \\ \end{eqnarray*}

Answer 2

The next step is to use convolution: $$\left(\sum_{k\ge 0} a_k x^k\right)\left(\sum_{k\ge 0} b_k x^k\right)=\sum_{k\ge 0} c_k x^k,$$ where $c_k = \sum_{j=0}^k a_j b_{k-j}$.

Answer 3

I add yet another answer, even though Rob's answer is definitive, hoping to make things even clearer. As we saw, from $$ (1+x)^{m+n}=(1+x)^m(1+x)^n$$ we infer that $$ \sum_{r=0}^\infty \binom{n+m}{r}x^r=\sum_{\rho=0}^\infty \sum_{\sigma=0}^\infty \binom{m}{\rho}\binom{n}{\sigma}x^{\rho+\sigma}.$$ Ok, so the coefficients of the two power series need be the same, that is $$ \binom{m+n}{r}=\sum_{\rho+\sigma=r} \binom{m}{\rho}\binom{n}{\sigma}=\sum_{\sigma=0}^r \binom{m}{r-\sigma}\binom{n}{\sigma},$$ which is the Vandermonde identity. (To obtain the second sum from the first, we have used the change of variable $\rho=r-\sigma$).