Applying binomial theorem to prove combinatorics identity

[Orange-Juice]

Homework Statement

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

Homework Equations

Binomial theorem

The Attempt at a Solution

[/B]
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 can't see how this is in any way rigorously justified. Can someone help me see the justification for simplifying the left side? Thanks.

 

[SteamKing]

Homework Statement

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

Homework Equations

Binomial theorem

The Attempt at a Solution

[/B]
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 can't see how this is in any way rigorously justified. Can someone help me see the justification for simplifying the left side? Thanks.

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

 

[nrqed]

Homework Statement

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

Homework Equations

Binomial theorem

The Attempt at a Solution

[/B]
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 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.

 

[Ray Vickson]

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

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

 

[SteamKing]

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

All I know is that:

Homework Statement

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

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

 

[haruspex]

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

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

 

[SteamKing]

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.

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.

 

[haruspex]

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.

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.

 

[Ray Vickson]

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.

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.