7
$\begingroup$

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

  • 0
    Indeed it is if you look at the right hand side of the e$x$pression. 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.2012-08-29

5 Answers 5

2

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

10

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

  • 0
    that was very very helpful, thank you!2012-08-29
9

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.

  • 0
    @robjohn Cool, thanks.2013-07-22
6

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

4

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.