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