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

  • $\begingroup$ 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. $\endgroup$ Aug 29 '12 at 7:44
  • $\begingroup$ 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}$? $\endgroup$
    – FRD
    Aug 29 '12 at 7:49
  • 2
    $\begingroup$ See also: Does this qualify as a proof? (Spivak's 'Calculus') and Combinatorial interpretation for the identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?. (And maybe some questions linked to these questions.) $\endgroup$ Aug 29 '12 at 8:23
  • $\begingroup$ 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. $\endgroup$ Aug 29 '12 at 8:43

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

  • $\begingroup$ that was very very helpful, thank you! $\endgroup$
    – FRD
    Aug 29 '12 at 19:47

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.

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.