Properties of Sigma sum

I am trying to prove that

$$\sum_{k=0}^{l} \binom{n}{k} \binom{m}{l-k} = \binom{n+m}{l} $$ use $(1+x)^{n}(1+x)^{m}$.

The book suggests the following solution

$$\sum_{k=0}^{n} \binom{n}{k} x^{k} \sum_{j=0}^{m} \binom{m}{j} x^{j} = \sum_{l=0}^{n+m} \binom{n+m}{l} x^{l}$$ where

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

I understand the idea of how the formula to prove it makes sense, but I cannot finish wrapping my head around why $x^{l}$ has that value. Then again, I understand its value and how it fits, but not how I could deduce such value on my own in another exercise.

I am looking for help finishing my proof, but I am not looking for an intuitive way to understand it or an alternative answer to my attempt. I would appreciate very much if somebody would help me figure out if my idea is right, or if not, what I am missing. My attempt goes as follows:

$$(1+x)^{n}(1+x)^{m}= \sum_{r=0}^{n} \binom{n}{r} x^{r} \sum_{s=0}^{m} \binom{m}{s} x^{s}$$ Now, lets define l as $l=r+s$, such that $s=l-r$, so we have

$$= \sum_{r=0}^{n} \binom{n}{r} x^{r} \sum_{l-r=0}^{m} \binom{m}{l-r} x^{l-r}$$ $$= \sum_{r=0}^{n}\sum_{l-r=0}^{m} \binom{m}{l-r} x^{l-r} \binom{n}{r} x^{r} $$

And this is where I am stuck. The only way I can turn this into the correct answer is by saying

$$= \sum_{r+l-r=0}^{n+m} \binom{n+m}{r-l-r} x^{r-l-r} = \sum_{l=0}^{n+m} \binom{n+m}{l} x^{l}$$ by saying that the sum of the terms $x^{l}$ is equivalent to $x_{r_{1}}(x_{s_{1}}+x_{s_{2}}+...) + x_{r_{2}}(x_{s_{1}}+x_{s_{2}}+...) + x_{r_{3}}(x_{s_{1}}+x_{s_{2}}+...) + ...$

Is that equivalence correct? If that is not right, how can I turn my attempt into the right answer? How can I know the value of $x^{l}$ just by looking at the solution from the book since that it seems to suggest it is obvious?

In your derivation:

Now, lets define l as $l=r+s$, such that $s=l-r$, so we have \begin{align*} \ldots = \sum_{r=0}^{n} \binom{n}{r} x^{r} \sum_{\color{blue}{l-r=0}}^{\color{blue}{m}} \binom{m}{l-r} x^{l-r}\tag{1} \end{align*}

it is the index region in the inner sum (1) which needs to be revised. Note, from (1) we obtain \begin{align*} \sum_{r=0}^{n}& \binom{n}{r} x^{r} \sum_{\color{blue}{l=r}}^{\color{blue}{m}} \binom{m}{l-r} x^{l-r}\tag{1.1}\\ &= \sum_{r=0}^{n}\sum_{\color{blue}{l=r}}^{\color{blue}{m}} \binom{m}{l-r} x^{l-r} \binom{n}{r} x^{r}\tag{1.2}\\ &= \sum_{r=0}^{n}\sum_{\color{blue}{l=r}}^{\color{blue}{m}} \binom{m}{l-r} \binom{n}{r} x^{l}\tag{1.3}\\ \end{align*}

Comment:

• In (1.1) we use a more common notation to write the lower limit of the inner sum without changing anything else

• In (1.2) we follow your next step

• In (1.3) we collect the terms in $x$ and get $x^{l-r}x^r = x^{(l-r)+r}=x^l$.

We observe in (1.3) the expression is a polynomial in $x$ with degree $\leq m$ since $r\leq l \leq m$. But we know from \begin{align*} (1+x)^n(1+x)^m=(1+x)^{n+m}\tag{2} \end{align*} the degree of the polynomial in $x$ in (2) is $\color{blue}{n+m}$. So, something was wrong.

In fact when substituting $l=r+s$ we have to respect the valid index range of the newly introduced index variable $l$. We have \begin{align*} \color{blue}{\left.\begin{array}{l} 0\leq r \leq n\\ 0\leq s\leq m \end{array}\right\} \qquad\to\qquad 0\leq r+s=l\leq n+m}\tag{3} \end{align*} We see the index range of $l$ is not $r\leq l\leq m$ as used in (1.1) to (1.3) but $0\leq l\leq n+m$ instead as stated in (3). With this correction we are on the right track again, since now we can write \begin{align*} (1+x)^n(1+x)^m&=\sum_{r=0}^{n} \binom{n}{r} x^{r} \sum_{s=0}^{m} \binom{m}{s} x^{s}\\ &=\sum_{r=0}^n\sum_{s=0}^m\binom{n}{r}\binom{m}{s}x^{r+s}\\ &=\sum_{l=0}^{m+n}\left(\sum_{{r+s=l}\atop{r\geq 0, s\geq 0}}\binom{n}{r}\binom{m}{s}\right)x^l\tag{3.1}\\ &=\sum_{l=0}^{m+n}\left(\sum_{r=0}^{l}\binom{n}{r}\binom{m}{l-r}\right)x^l\tag{3.2}\\ \end{align*} Since we have $(1+x)^n(1+x)^m=(1+x)^{n+m}=\sum_{l=0}^{n+m}\binom{n+m}{l}x^l$ the claim follows by coefficient comparison with (3.2) of alike powers in $x$.

Comment:

• In (3.1) we introduce $l=r+s$ and rearrance the polynomial according increasing powers of $l$.

• In (3.2) we eliminate $r$ using $r=l-s$.