# Applying binomial theorem to prove combinatorics identity

1. Dec 13, 2015

### Orange-Juice

1. The problem statement, all variables and given/known data
Prove that $$\sum\limits_{k=0}^l{n \choose k}{m \choose l-k} = {n+m \choose k}$$

2. Relevant equations
Binomial theorem

3. The attempt at a solution

We know that $$(1+x)^n(1+x)^m = (1+x)^{n+m}$$
which, by the binomial theorem, is equivalent to:
$${\sum\limits_{k=0}^n{n \choose k}x^k}{\sum\limits_{j=0}^m{m \choose j}x^j} = {\sum\limits_{l=0}^{n+m}{n+m \choose l}x^l}$$
The solution involves setting $$l = j+k$$ and then simplifying the left side to:
$${\sum\limits_{k=0}^l{n \choose k}{m \choose l-k}x^l}$$ but I cant see how this is in any way rigorously justified. Can someone help me see the justification for simplifying the left side? Thanks.

2. Dec 13, 2015

### SteamKing

Staff Emeritus
Have you tried applying the definition of ${n \choose k} = \frac{n!}{k!(n-k)!}$ to the terms in the summations?

3. Dec 13, 2015

### nrqed

The key point is that this must be true for any value of x, which implies that the two sides must be equal for each choice of power of x. That means that the identity can be made much stronger by imposing the equality for each separate power of x. So the coefficient of x to some power on one side must be equal to the coefficient of the term with the same power of x on the other side, this leads to your result with j+k=l.

4. Dec 13, 2015

### Ray Vickson

Are you saying you do not understand why
$$\sum_k c_k x^k \; \sum_j d_j x^j = \sum_l \left(\sum_k c_k d_{l-k} \right) x^l \;?$$
It is a standard result in elementary algebra. All you are doing is gathering together the coefficients of $x^k \cdot x^j =x^{k+j}$ for each constant value of $l = k+j$.

5. Dec 13, 2015

### SteamKing

Staff Emeritus
All I know is that:

It seems to me, from a purely uninformed point of view, that bringing the binomial theorem into this proof just complicates things.

6. Dec 13, 2015

### haruspex

As I understand the OP, the object of the exercise is to use the binomial theorem to establish the identity. Whether there is a better way is beside the point.
Specifically, the question is how the product of the two sums collapses to the single sum, k=0 to l.
@Orange-Juice , the method sets l=j+k, so j=l-k. Substitute that in the summation, rewrite it as a double sum, and change the order of the summation.
Note that you are wrong about what the left hand side needs to become. You missed an enclosing $\Sigma_{l=0}^{n+m}$

7. Dec 13, 2015

### SteamKing

Staff Emeritus
That's just it. The problem statement simply says, "Prove such and such." It doesn't say "Using the binomial theorem, prove such and such."

I think the OP has just thrown the binomial theorem in because he doesn't have anything else to put in Section 2 of the HW template. The summations don't even involve binomials.

8. Dec 13, 2015

### haruspex

The OP says "the solution involves setting...". Either that is a hint provided (in conjunction with a hint or direction to use the binomial theorem), or OJ is trying to follow a solution that uses the binomial theorem. Either way, the question OJ presents is how a particular step works.

9. Dec 14, 2015

### Ray Vickson

Using the binomial expansion to prove the result is the more-or-less standard way of doing it; it is the first thing I would have done if I were asked to prove the identity. The close connection between the "binomial coefficients" and the "binomial expansion" cries out to be used.