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}$."?

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

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.