5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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$$ $\endgroup$ – Severin Schraven Nov 12 '17 at 15:51
5
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Ok so: \begin{align} (1+x)^m(1+x)^n &=\sum_{k=0}^m\binom{m}{k}x^k\sum_{j=0}^n\binom{n}{j}x^j\\ &=\sum_{k=0}^m\sum_{j=0}^n\binom{m}{k}\binom{n}{j}x^{k+j}\\ &=\sum_{k=0}^m\sum_{l=k}^n\binom{m}{k}\binom{n}{k-l}x^r&with j=l+k\\ &=\sum_{l=0}^m{\sum_{k=0}^l\binom{m}{k}\binom{n}{k-l}}x^l\\\ \to(1+x)^{m+n} &=\sum_{l=0}^{m+n}{\binom{m+n}{l}}x^l \end{align} . Hope this is right.. $\endgroup$ – MatheSt Nov 12 '17 at 16:34
  • 1
    $\begingroup$ @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$. $\endgroup$ – Markus Scheuer Nov 12 '17 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.