# Proving this binomial identity

I'm required to prove the following binomial identity:

$$\sum\limits_{k=0}^l {n \choose k} {m \choose l-k} = {n+m \choose l}$$

I tried various arrangements but reached nowhere. Finally I turned to the hint in the book, which says

Apply the binomial theorem to $(1+x)^n (1+x)^m$

And suddenly, it makes sense. All I now need to do is add the powers on the right-hand side and equate the coefficients of $x^l$. But I'm wondering how to write a proper proof. Will it be enough if I say:

$(1+x)^n (1+x)^m = (1+x)^{m+n}$

Applying the binomial theorem separately for the two terms on the LHS and collecting the coefficients of $x^l$ on both sides, we have:

$${n \choose 0} {m \choose l} + {n \choose 1} {m \choose l-1} + \ldots + {n \choose l}{m \choose 0} = {n+m \choose l}$$

Is this enough? I don't know why but it looks rather shallow to me.

• Your proof is correct. I am not sure what is bothering you. If you want to prove that necessarily the coefficients of $x^l$ are equal, you can note that both the LHS and RHS are polynomials of the variable $x$, therefore they coincide on $\mathbb{R}$ if and only if they have the same coefficients. – Ian May 9 '14 at 4:37
• @Ian: Thanks a lot! You know how it is ... when a proof is so short and "obvious" you start wondering if it's correct. ;) – dotslash May 9 '14 at 4:38
• yes it is right.One should always be able to do such easy sums.I believe. @ dotslash – soumajit das May 9 '14 at 4:52
• There are several posts about this identity: See this question and other posts, which are linked there. – Martin Sleziak May 10 '14 at 16:23

Other proof is counting in two ways: what the number of choose $l$ balls in $m+n$? (the balls are enumerate -- 1,2,...,m+n)
for one side: $\binom{m+n}{l}$
for other side: divided the balls into 2 groups, group 1 with $n$ balls and group 2 with $m$ balls. If we choose $k$ balls in group 1, we should choose $l-k$ balls in group 2. So, we have $\sum\limits_{k=0}^l {n \choose k} {m \choose l-k} = {n+m \choose l}$