Answer book is unclear to me on the following question. Would apreciate if someone could clear it up for me. Thanks in advance.
"Calculus 3rd Edition" by Michael Spivak — Chapter 2 Problem 4 (a) states:
Prove that
$$\sum_{k=0}^l{n\choose k}{m\choose l-k}={n+m\choose l}$$
Hint: Apply the binomial theorem to $(1+x)^n(1+x)^m$.
"Answer Book for Calculus" shows the following answer:
Since
$$(1+x)^n(1+x)^m=(1+x)^{n+m}$$
we have
$$\sum_{k=0}^n {n\choose k}x^k\cdot\sum_{j=0}^m{m\choose j}x^j=\sum_{l=0}^{n+m}{n+m\choose l}x^l$$
(so far no problem) ***
But the coefficient of $x^l$ on the left is clearly
$$\sum_{k=0}^l{n\choose k}{m\choose l-k},$$
one term of the sum ocurring for each pair $k,j=l-k$.
I can´t seem to understand what comes after "***" ¿How did he arrive at $\sum_{k=0}^l{n\choose k}{m\choose l-k}$? ¿How would this prove the initial statement?
Best Answer
Suppose $p,q$ are polynomials, then we have $p(x)=\sum_i p_i x^i$ and $q(x) = \sum_j q_j x^j$ where for convenience I am assuming that $p_i, q_j$ are non zero for a finite number of terms.
If $p(x)=q(x)$ for all $x$ it is straightforward to show using evaluation & differentiation that $p_k=q_k$ for all $k$.
If $r(x) = p(x) q(x)$, then $r(x) = \sum_i \sum_j p_i q_j x^{i+j}$. Using the transformation $l=i+j, j=j$, we have $r(x)= \sum_l ( \sum_j p_{l-j} q_j ) x^l$. That is, the $l$th coefficient of $r$ is $ \sum_j p_{l-j} q_j $.
Now let $p(x)= (1+x)^m$, $q(x) = (1+x)^n$, $r(x) = (1+x)^{m+n}$.
The $l$th coefficient (I'm taking $l \in \{0,...,m+n\}$ here) of $r$ is $\binom{n+m}{l}$, and, using the formula above we have $ \sum_j p_{l-j} q_j $ and we have $ \sum_j p_{l-j} q_j = \sum_{j=0}^l \binom{n}{j} \binom{m}{l-j}$.
Note that $\binom{n}{j} = 0$ for $j >n$, and similarly for the other term.