Spivak's Calculus - Exercise 4.a of 2nd chapter 
4 . (a) Prove that
  $$\sum_{k=0}^l \binom{n}{k} \binom{m}{l-k} = \binom{n+m}{l}.$$
  Hint: Apply the binomial theorem to $(1+x)^n(1+x)^m$.

I'm having a hard time trying to solve the problem above. I've done all of the previous exercises of the 2nd chapter with little difficulty, so far. I think I might be missing a trivial point somewhere.

The answer I got from the Answer Book, and is not very helpful either... :(

 4. (a) Since $(1+x)^n(1+x)^m = (1+x)^{n+m}$
 we have
 $$\sum_{k=0}^n \binom{n}{k}x^k\cdot\sum_{j=0}^m \binom{m}{j}x^j\cdot=\sum_{l=0}^{n+m} \binom{n+m}{l}x^l$$
 But the coefficient of $x^l$ on the left is clearly $$\sum_{k=0}^l\binom{n}{k}\binom{m}{l-k}.$$
 One term of the sum occurring for each pair $k$, $j = l-k$.  

I couldn't get the last part of the answer:
why is it that the "coefficient of $x^l$ on the left is clearly $\sum_{k=0}^l\binom{n}{k}\binom{m}{l-k}$."?
 A: Note that since $\binom{n}{k} = {n (n-1)\cdots (n-k+1) \over k!}$, we can let $\binom{n}{k} = 0 $ if $k > n$. This will simplify notation.
Adopting this convention, we get
$\sum_{k=0}^\infty \binom{n}{k}x^k\cdot\sum_{j=0}^\infty \binom{m}{j}x^j = \sum_{k=0}^\infty \sum_{j=0}^\infty \binom{n}{k} \binom{m}{j}x^{k+j}$.
Let $I_1 = \{ (k,j) | k, j \ge 0 \}$ and $I_2 = \{ (p,l) | 0 \le p \le l \}$, then we have
$I_1 = \{ (p, l-p) | (p,l) \in I_2 \}$.
Here is one way to see this: Define the linear operator $\phi((x,y) = (x,x+y)$, the inverse is $\phi^{-1} ((x,y)) = (x,y-x)$. It is straighforward to check that $\phi(I_1) \subset I_2$ and $\phi^{-1}(I_2) \subset I_1$, hence $\phi(I_1) = I_2$.
In particular, $f$ is zero for all but a finite number of terms, we have
$\sum_{(k,j) \in I_1} f(k,j) = \sum_{(p,l) \in I_2} f(p,l-p)$.
Hence we can write
\begin{eqnarray}
\sum_{(k,j) \in I_1} \binom{n}{k} \binom{m}{j}x^{k+j} &=& \sum_{k=0}^\infty \sum_{j=0}^\infty \binom{n}{k} \binom{m}{j}x^{k+j} \\
&=& \sum_{(p,l) \in I_2} \binom{n}{p} \binom{m}{l-p}x^{l} \\
&=& \sum_{l=0}^{^\infty} \sum_{p=0}^l \binom{n}{p} \binom{m}{l-p}x^{l}
\end{eqnarray}
Now we have
$$\sum_{l=0}^{^\infty} \sum_{p=0}^l \binom{n}{p} \binom{m}{l-p}x^{l} = \sum_{l=0}^{^\infty} \binom{n+m}{l}x^l ,$$
which are polynomials of $x$ on both sides (note that only a finite number of coefficients can be non zero). Since this equality is true for all $x$, the polynomials are equal and hence so are the coefficients of each $x^l$ (differentiate $l$ times and set $x=0$ to convince yourself). It follows that
$$\sum_{p=0}^l \binom{n}{p} \binom{m}{l-p} = \binom{n+m}{l} .$$
A: If you multiply $c_0+c_1x+\cdots+c_nx^n$ by $d_0+d_1x+\cdots+d_mx^m$, then for $k\leq\min(n,m)$ you will get terms involving $x^k$ from the products $c_0\times d_kx^k$, $\,c_1x\times d_{k-1}x^{k-1}$, $\,c_2x^2\times d_{k-2}x^{k-2}$,..., $c_kx^k\times d_0$, and from no other products. Adding those contributions gives $(c_0d_k+c_1d_{k-1}+c_2d_{k-2}+\cdots+c_kd_0)x^k$. Even if one should have $k>\min(n,m)$, the coefficient of $x^k$ is clearly always the sum of all $c_id_j$ with $i+j=k$, which you can write as $\sum_{i=0}^kc_id_{k-i}$ provided one defines $c_i$ or $d_j$ to be $0$ when the subscript is too large. And in your example the binomial coefficient expressions indeed become $0$ when the lower index is too large.
A: You should determine the coefficient of $x^l$ in $(1+x)^n(1+x)^m$ in two ways. First multiply this out to get $(1+x)^n(1+x)^m=(1+x)^{n+m}$.  So considering the right hand side and using the binomial theorem we get $\binom{n+m}{l}$. 
Now consider the coefficient of $x^l$ in the left hand side after expanding each term using the binomial theorem
$$(1+x)^n(1+x)^m=(\sum_{p=0}^m \binom{m}{p}x^p)(\sum_{q=0}^n \binom{n}{q}x^q)$$ You get a coefficient of $x^l$ in the product when you multiply $\binom{m}{p}x^p\binom{n}{q}x^q$ when $p+q=l$, i.e. $q=l-p$. 
Then we have to take into account all the ways this can happen and comparing it to what we got on the right side so we have
$$\sum_{p=0}^l\binom{m}{p}\binom{n}{l-p}=\binom{m+n}{l}$$
A: Maybe this will help you think about the coefficients. We have $n$ boys and $m$ girls, and we want to form a committee of $l$ people from these $n+m$ people. Clearly there are $\binom{n+m}{l}$ ways to form the committee.
Let's count the number of committees another way. We could have $0$ boys and $l$ girls. Such a committee can be formed in $\binom{n}{0}\binom{m}{l}$ ways.
Or we could have $1$ boy and $l-1$ girls. Such a committee can be formed in $\binom{n}{1}\binom{m}{l-1}$ ways.
Or we could have $2$ boys and $l-2$ girls. Such a committee can be formed in $\binom{n}{2}\binom{m}{l-2}$ ways.
Continue. The total number of committees is
$$\sum_{k=0}^l \binom{n}{k}\binom{m}{l-k}.\tag{$1$}$$
But we already saw that the number of committees is $\binom{n+m}{l}$.
Note: It is possible that for example there is a total of $3$ boys and $24$ girls, and we want to form a committee of $7$ people. Then the formula appears to break down. But it doesn't if we agree that $\binom{a}{b}=0$ if $b\gt a$.
To apply the reasoning to $(1+x)^n(1+x)^m$, you might first look at $(1+x)^n(1+y)^m$, and set $y=x$ at the end. So expand both, multiply. For fixed $l$, gather together terms that have a combined total of $l$ $x$'s (boys) and/or $y$'s. The total number will be given by Formula $(1)$.
A: Multiplication of formal power series is performed by collecting the terms with the same powers of $x$:
$$
\begin{align}
\left(\sum_{k=0}^\infty a_kx^k\right)\left(\sum_{k=0}^\infty b_kx^k\right)
&=\sum_{k=0}^\infty\left(\sum_{j=0}^k a_j\color{#C00000}{x^j}b_{k-j}\color{#C00000}{x^{k-j}}\right)\\
&=\sum_{k=0}^\infty\left(\sum_{j=0}^k a_jb_{k-j}\right)\color{#C00000}{x^k}\tag{1}
\end{align}
$$
Note that the subscripts in the inner sum add up to $k$, the power of $x$ in the outer sum.
Apply $(1)$ to the product of
$$
(1+x)^m=\sum_{k=0}^\infty\binom{m}{k}x^k\tag{2}
$$
and
$$
(1+x)^n=\sum_{k=0}^\infty\binom{n}{k}x^k\tag{3}
$$
which is
$$
(1+x)^{m+n}=\sum_{k=0}^\infty\binom{m+n}{k}x^k\tag{4}
$$
I extended the indices in the sums to $\infty$ since for $k>n$, $\binom{n}{k}=0$.
For the product of $(2)$ and $(3)$, we get
$$
(1+x)^m(1+x)^n=\sum_{k=0}^\infty\left(\sum_{j=0}^k \binom{m}{j}\binom{n}{k-j}\right)x^k\tag{5}
$$
Comparing the coefficients of $x^k$ in $(4)$ and $(5)$ yields
$$
\binom{m+n}{k}=\sum_{j=0}^k \binom{m}{j}\binom{n}{k-j}\tag{6}
$$
as desired.
A: I thought proof by induction would be interesting which uses a property of Pascal's triangle. Assume it is true for $<l$. Induction on $n+m$. For $n=0$ it is true. Assume that it is true for $n$. For $n+1$,
$$\binom{n+1+m}{l}=\sum_{k=0}^l\binom{n+1}{k}\binom{m}{l-k}=\sum_{k=0}^l\left[\binom{n}{k}+\binom{n}{k-1}\right]\binom{m}{l-k}=\hspace{1cm}\binom{n+m}{l}+\sum_{k=1}^l\binom{n}{k-1}\binom{m}{l-k}$$
Hence we get
$$\binom{n+1+m}{l}-\binom{n+m}{l}=\sum_{k+1=1}^{k+1=l}\binom{n}{(k+1)-1}\binom{m}{l-(k+1)}$$
$$\binom{n+m}{l-1}=\sum_{k=0}^{l-1}\binom{n}{k}\binom{m}{(l-1)-k}$$
which is true by induction..
