Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


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

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|cite|improve this answer
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

Your Answer


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.