# Applying binomial theorem to prove combinatorics identity

• Orange-Juice
In summary: 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...
Orange-Juice

## Homework Statement

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

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.

Orange-Juice said:

## Homework Statement

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

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?

Orange-Juice said:

## Homework Statement

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

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.

SteamKing said:
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##.

Ray Vickson said:
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:

Orange-Juice said:

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

SteamKing said:
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}##

haruspex said:
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.

SteamKing said:
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.

SteamKing said:
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.

## 1. How is the binomial theorem used to prove combinatorics identities?

The binomial theorem is a mathematical formula that allows us to expand expressions of the form (a + b)^n, where a and b are any real numbers and n is a positive integer. By applying this theorem, we can generate a series of terms that represent the coefficients of the expanded expression. These terms can then be rearranged and simplified to prove various combinatorics identities.

## 2. Can you provide an example of using the binomial theorem to prove a combinatorics identity?

One example is the identity nCr = n! / r!(n-r)!, where nCr represents the number of ways to choose r objects from a set of n objects. Using the binomial theorem, we can expand (1+x)^n and then equate the coefficients of x^r on both sides to prove this identity.

## 3. Are there any limitations to using the binomial theorem to prove combinatorics identities?

Yes, the binomial theorem can only be used for identities involving binomial coefficients, which are expressions of the form nCr. It cannot be applied to prove other types of combinatorics identities, such as those involving permutations or combinations with repetition.

## 4. Is the binomial theorem the only method for proving combinatorics identities?

No, there are other methods such as algebraic manipulation, mathematical induction, and graphical representations that can also be used to prove combinatorics identities. The binomial theorem is just one tool that can be used, but it is particularly useful for identities involving binomial coefficients.

## 5. How important is understanding the binomial theorem for studying combinatorics?

Understanding the binomial theorem is essential for studying combinatorics, as it allows us to solve many problems involving counting and choosing. It also provides a deeper understanding of the relationships between different combinatorics identities and can be applied in various other areas of mathematics and science.

Replies
9
Views
598
Replies
1
Views
2K
Replies
5
Views
2K
Replies
10
Views
2K
Replies
7
Views
1K
Replies
3
Views
1K
Replies
6
Views
785
Replies
5
Views
3K
Replies
15
Views
2K
Replies
13
Views
2K