7
$\begingroup$

Answer in the textbook: $\sum_{k=0}^{4} \binom{12}{9-k}\binom{4}{k}$

Can I just multiply the two terms together to get $(1+x)^{16}$ then apply the binomial coefficient theorem?

I don't know how they got the sum at the end, I was only taught how to find the coefficient of a term in one binomial expansion using the binomial coefficient theorem...

$\endgroup$
  • 2
    $\begingroup$ It is indeed equal to $(1+x)^{16}$ so your method seems correct to me. $\endgroup$ – Zubzub Dec 9 '17 at 18:58
10
$\begingroup$

You've stumbled across a case of the Vandermonde identity:

$$ \sum_{k=0}^r{m\choose k}{n\choose r-k} = {m + n\choose r} $$

So you are indeed correct, the answer is equivalent to the coefficient of $x^9$ in $(1+x)^{16}$, since $$ {16\choose 9} = \sum_{k=0}^9{4\choose k}{12\choose 9-k} $$ To obtain the second form, note that $$ \begin{aligned} \ [x^9](1+x)^{12}(1+x)^4 & = [x^9]\left(\sum_{k=0}^{12}{12\choose k}x^k\right)\left(\sum_{k=0}^4{4\choose k}x^k\right) \\ & = [x^9]\sum_{k=0}^{12+4}x^k\left(\sum_{i,j\ge0,\ i+j=k}{4\choose i}{12\choose j}\right) \\ & = [x^9]\sum_{k=0}^{16}x^k\left(\sum_{j=1}^{k}{4\choose j}{12\choose k-j}\right) \\ & = \sum_{j=0}^9{4\choose k}{12\choose 9-k} \end{aligned} $$

Going from the first line to the second line, we've essentially used a finite version of the Cauchy Product, and to go from the inner sum on the second line to the inner sum on the third line, note that if $i+j=k$, then $i=k-j$, so really we only care about $j$.

$\endgroup$
  • $\begingroup$ oh yes, I have heard of this identity before! Thank you for making it very clear! $\endgroup$ – numericalorange Dec 9 '17 at 20:24
3
$\begingroup$

If you think about this as choosing objects, the result is actually very intuitive. Picture twelve copies of $(1+x)$ laid out. The only way to get a term of $x^9$ when we expand is to pick exactly $9$ $x$'s and $7$ $1$'s. Alternatively, if we have $12$ copies of $(1+x)$ followed by $4$ more, we can imagine picking the first $k$ $x$'s from the first $12$, and the remaining $9-k$ from the next $4$.

$\endgroup$
  • 1
    $\begingroup$ Very nice way to picture it! Thanks! $\endgroup$ – numericalorange Dec 9 '17 at 20:23
1
$\begingroup$

Yes, you can easily put them together to get $(1+x)^{16}$. But, I think that textbook wants you to learn how to split the binomial up. So, in this the reason they have a sum in the answer is because there are many ways to $x^9$. A couple of the ways are $x^0$ from the first term and $x^9$ from the second $x^1$ from the first term, and $x^8$ from the second term, $x^2$ from the first term and $x^7$ from the second term, etc. Summing all of the coefficients up and then compressing it into sigma notation creates their answer. For me, I would obviously do it your way, but I think the book wants you to take something away from it :D

The two answers are in fact equal. Check out the Vandermonde identity.

$\endgroup$
  • $\begingroup$ Oh, I understand why they decided to do that then! Thanks! $\endgroup$ – numericalorange Dec 9 '17 at 20:23
1
$\begingroup$

The factorization $(1+x)^{12}(1+x)^4$ is not accidental here. Let's expand by using Binomial Theorem:

$$\sum_{k=0}^{12}\binom{12}{k}x^k\cdot\sum_{m=0}^{4}\binom{4}{m}x^m.$$

What about $x^9$ in this expansion? We get this power when $k=9,m=0$, $k=8,m=1$, $k=7,m=2$, $k=6,m=3$ and finally $k=5,m=4$. Then our coefficient is $$\binom{12}{9}\cdot\binom{4}{0}+\binom{12}{8}\cdot\binom{4}{1}+\binom{12}{7}\cdot\binom{4}{2}+\binom{12}{6}\cdot\binom{4}{3}+\binom{12}{5}\cdot\binom{4}{4}.$$ It's that!!!

$\endgroup$
  • $\begingroup$ Oh, I understand! Thank you!! $\endgroup$ – numericalorange Dec 9 '17 at 20:23

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.