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$
1
  • 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$ Nov 12, 2017 at 15:51

2 Answers 2

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$
2
  • 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, 2017 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$ Nov 12, 2017 at 17:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .