Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
2  
    
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

5 Answers 5

up vote 7 down vote accepted

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.

share|improve this answer
    
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)$.

share|improve this answer
    
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} .$$

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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