Binomial-Theorem proof

Question

I have the following problem:

$n,m \in \mathbb{N_0}$. Write $(1+x)^{n+m}=(1+x)^{n}(1+x)^{m}$ with the help of binomial formulas, multiply the right side, and deduce the following Identity between binomial coefficients:

$\begin{pmatrix} n+m\\k\\ \end{pmatrix}= \sum_{l=0}^{k}{\begin{pmatrix} n\\l\\ \end{pmatrix}}{\begin{pmatrix} m\\k-l\\ \end{pmatrix}} \forall k \in \mathbb{N_0}$

My idea: I know that: $(a+b)^n=\sum_{k=0}^{n}{\begin{pmatrix} n\\k\\ \end{pmatrix}a^{n-k}b^k=\sum_{k=0}^{n}{\begin{pmatrix} n\\k\\ \end{pmatrix}a^{k}b^{n-k}}}$

So:$(1+x)^{n+m}=\sum_{k=0}^{n}{{\begin{pmatrix} n\\k\\ \end{pmatrix}x^k}*\sum_{k=0}^{n}{{\begin{pmatrix} m\\k\\ \end{pmatrix}x^k}}} =\sum_{k=0}^{n}{{\begin{pmatrix} n+m\\k\\ \end{pmatrix}x^k}}=(1+x)^{n+m}$ But this doens't seem right.. Can anyone help me here?

Answer 1

We obtain \begin{align*} \sum_{k=0}^{n+m}\color{blue}{\binom{n+m}{k}}x^k &=(1+x)^{n+m}=(1+x)^n(1+x)^m\\ &=\sum_{l=0}^n\binom{n}{l}x^l\sum_{j=0}^m\binom{m}{j}x^j\\ &=\sum_{k\geq 0}\left(\sum_{{l+j=k}\atop{k,j\geq 0}}\binom{n}{l}\binom{m}{j}\right)x^k\tag{1}\\ &=\sum_{k\geq 0}\left(\color{blue}{\sum_{l=0}^k\binom{n}{l}\binom{m}{k-l}}\right)x^k\tag{2}\\ \end{align*}

Comment:

• In (1) we apply the Cauchy product formula. Observe the series starting with index $k=0$ is finite since $\binom{r}{k}=0$ if $k>r$, $r\in\mathbb{N}$.

• In (2) we set the upper limit of the inner series to $k$ since $\binom{m}{k-l}=0$ if $l\geq k$.

Answer 2

HINT The coefficient of $x^k$ on the left hand side is $n+m \choose k$. Now calculate the coefficient of $x^k$ on the right hand side using binomial theorem.