Prove $\sum_{k=0}^l \binom{n}{k}\binom{m}{l-k} = \binom{n+m}{l}$

Question

$$\sum_{k=0}^l \binom{n}{k}\binom{m}{l-k} = \binom{n+m}{l} $$

There was a hint saying apply binomial theorem to $(1+x)^n(1+x)^m$

From which I've got $(1+x)^n(1+x)^m=(1+x)^{m+n}$

1. $(1+x)^n(1+x)^m=\sum^n_{k=0}\binom{n}{k}x^k\cdot\sum^m_{j=0}\binom{m}{j}x^j$

2. $(1+x)^{m+n}=\sum^{m+n}_{l=0}\binom{m+n}{l}x^l$

3. $\sum^n_{k=0}\binom{n}{k}x^k\cdot\sum^m_{j=0}\binom{m}{j}x^j = \sum^{m+n}_{l=0}\binom{m+n}{l}x^l$

In (3) every power $l$ of $x$ on the RHS equals $k+j$ for some $k$ and $j$ from the LHS. Here I'm stuck. How to complete the proof?

Answer 1

Rewrite $$\sum^m_{j=0}\binom{m}{j}x^j\cdot\sum^n_{k=0}\binom{n}{k}x^k$$ as ($l=j+k$) $$\sum^{m+n}_{l=0}\sum^{l}_{k=0}\binom{m}{l-k}x^{l-k}\binom{n}{k}x^k =\sum^{m+n}_{l=0}\left[\sum^{l}_{k=0}\binom{m}{l-k}\binom{n}{k}x^l\right]$$

and compare the coefficient of $x^l$ on both sides of the equation, getting $$\sum^l_{k=0}\binom{m}{l-k}\binom{n}{k}=\binom{m+n}l$$ as desired.

Answer 2

Method 1

\begin{align*} \sum_{k=0}^n\binom{n}{k}x^k\sum_{i=0}^m\binom{m}{i}x^i&=\sum_{k=0}^n\sum_{i=0}^m\binom{n}{k}\binom{m}{i}x^{k+i}\\ &\underset{j=k+i}{=}\sum_{j=0}^{n+m}\sum_{k+i=j}\binom{n}{k}\binom{m}{i}x^j\\ &=\sum_{j=0}^{n+m}\sum_{k=0}^j\binom{n}{k}\binom{m}{j-k}x^j \end{align*} and thus, the claim follow.

Method 2

You want to do $\ell$ groups with $m$ men and $n$ women. Either you take $0$ woman and $\ell$ men, or you take $1$ moman and $\ell-1$ men, or you take $2$ women and $\ell-2$ men...