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