# Does this qualify as a proof? (Spivak's 'Calculus')

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.

-
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. –  Ｊ. Ｍ. Jul 24 '12 at 21:35

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

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