# Binomial-Theorem proof

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?

• It might be useful to remember Cauchy formula for the product of two polynomials: $$\left( \sum_{j=0}^n a_j x^j \right) \cdot \left( \sum_{k=0}^m b_k x^k \right) = \sum_{s=0}^{n+m} \left( \sum_{t=0}^s a_t b_{s-t} \right) x^s$$ – Severin Schraven Nov 12 '17 at 15:51

• 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$.
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.
• @MatheSt: Some corrections should be done. Check the third line: $r$ should be presumably $l$. In the second line we see $x^{k+j}$. Since the fourth line has $x^l$ we should substitute in the third line $l=k+j$. In the fourth line the summation of the inner sum starts with $k=0$, but then we have a negative lower part in $\binom{n}{k-l}$ if $l>0$. – Markus Scheuer Nov 12 '17 at 17:26