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

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

-
You need to locate the coefficient of $x^l$ - and this is done by picking out the relevant terms on the left hand side with $l=0+l=1+(l-1)=2+(l-2)=\dots=(l-1)+1=l+0$ - the sum adds all these coefficients together. – Mark Bennet Aug 29 '12 at 7:44
I'm sorry, what you said wasn't very clear to me. Isn't the "coefficient of $x^l$" mentioned simply $\binom{n+m}{l}$? – FRD Aug 29 '12 at 7:49
Indeed it is if you look at the right hand side of the expression. But if you look at the left hand side you find that this coefficient is split up into pieces - the sum of the pieces is equal to the coefficient - that is what the equation is saying. – Mark Bennet Aug 29 '12 at 8:43

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.

-
that was most helpful, thank you! – FRD Aug 29 '12 at 21:44
For understanding the first part, see this question . – Yam Marcovic Jul 22 '13 at 12:15
@YamMarcovic: that formula is known as the Cauchy Product. – robjohn Jul 22 '13 at 13:23
@robjohn Cool, thanks. – Yam Marcovic Jul 22 '13 at 19:02

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

-
that was very very helpful, thank you! – FRD Aug 29 '12 at 19:47

First note that $\sum_{k=0}^n \binom{n}{k}x^k\cdot\sum_{j=0}^m \binom{m}{j}x^j = \sum_{k=0}^n \sum_{j=0}^m \binom{n}{k} \binom{m}{j}x^{k+j}$.

Now notice that the summation is over the index set $\{(k,j) | k=0,...,n, \ j=0,...,m \}$. You need to convince yourself that this is the same as the index set $\{ (p,l-p) | l=0,...,n+m,\ p=0,...,l \}$, so we can write

$$\sum_{k=0}^n \sum_{j=0}^m \binom{n}{k} \binom{m}{j}x^{k+j} = \sum_{l=0}^{n+m} \sum_{p=0}^l \binom{n}{p} \binom{m}{l-p}x^{l}.$$ Now we have $$\sum_{l=0}^{n+m} \sum_{p=0}^l \binom{n}{p} \binom{m}{l-p}x^{l} = \sum_{l=0}^{n+m} \binom{n+m}{l}x^l ,$$ which are polynomials of $x$ on both sides. 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} .$$

-

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.

-

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

-