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.

I'm working through Spivak's 'Calculus' at the moment, and a question about series confused me a bit. I think I have the solution, but I'm not sure if my "proof" holds.

The question is:

Prove that $\sum\limits_{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}$

So I expanded $(1+x)^{n}(1+x)^{m}$, then expanded that again, and compared that to $(1+x)^{n+m}$, to get the equality:

$$\begin{align*} &\binom{n}{0}\binom{m}{0} + \left [ \binom{n}{0}\binom{m}{1} + \binom{n}{1}\binom{m}{0} \right ]x \\ &+ \left [ \binom{n}{0}\binom{m}{2} + \binom{n}{1}\binom{m}{1} + \binom{n}{2}\binom{m}{0} \right ]x^{2} + \cdots\\ &\qquad = \binom{n+m}{0} + \binom{n+m}{1}x + \binom{n+m}{2}x^{2} + \cdots \end{align*}$$

Now, my question is, is the original statement proven, just because the terms match up on both sides of the equality, or is this insufficient?

Thanks.

share|improve this question
1  
For completeness: what you have there is the well-known Chu-Vandermonde identity, about which much has been said. A strategy like yours is a common way to prove such convolution identities. –  J. M. Jul 24 '12 at 21:35
add comment

2 Answers 2

up vote 5 down vote accepted

Two polynomials are equal iff they have equal degree and equal coefficients.

This statement directly follows from the following fact: if $$ f(x)=\sum_{k=1}^m a_k x^k $$ then $$ a_k=\frac{f^{(k)}(0)}{k!} $$

share|improve this answer
    
Not the most detailed, but it's really all I needed, thanks. –  SiliconCelery Jul 24 '12 at 21:43
    
@SiliconCelery Do you know why this is true? If not, your proof might be circular. That's why Michael sketched a proof. See the links in my comment to Michael's answer. –  Bill Dubuque Jul 24 '12 at 22:22
add comment

It works as a proof if you know that two polynomials are equal only if their coefficients match.

If they're equal, then one of them minus the other is zero, regardless of the value of $x$. So now the problem is to show that a polynomial is zero for all $x$ only if its coefficients are zero. If it has a nonzero coefficient, find the one of lowest degree. If that's the zeroth-degree term, consider what happens when $x=0$. Otherwise, you've got $$ a_k x^k + \text{higher-degree terms} = x^k(a_k + \underbrace{a_{k+1}x + a_{k+2}x^2+\cdots+a_n x^n}). $$ Since $a_k\ne 0$, it's enough to show that one can make $x\ne0$ so small by comparision to all of $|a_k|,|a_{k+1},\ldots,|a_n|$ that the expression over the $\underbrace{\text{underbrace}}$ cannot cancel out $a_k$.

share|improve this answer
2  
Or use the factor theorem and induction as in this answer. See also the optimization in that thread using continuity of polynomials (hint: $\rm\:f(x)\equiv 0\:\Rightarrow\: f(x)/x\equiv 0).$ –  Bill Dubuque Jul 24 '12 at 22:17
add comment

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.