A coefficient problem involving combination

In summary, the given formula is correct and can be proven by using the binomial theorem. A substitution of variables can also be used, and a helpful lemma may be needed. The formula can be found in Spivak's Calculus, Chapter 2, Problem 4. Additionally, a result can be obtained by calculating the coefficient of x^{l} in the product (1-x)^{n}(1-x)^{m}.
  • #1
julypraise
110
0

Homework Statement


(1) Is the following formula right?
[itex]\sum_{l=0}^{m+n} \sum_{k=l-m}^{n} \binom nk \binom {m}{l-k} x^{l} = \sum_{k=0}^{n} \binom nk x^{k} \sum_{j=0}^{m} \binom mj x^{j}[/itex]

(2) If right, how do I prove it? If not, what is the right formula, and how do I prove it?

(3) Could you suggest any papers or relevant works that prove this result?

Homework Equations


No relevant equation exist.


The Attempt at a Solution


I've checked that, by specialization of the formula above, the formula is true for some special cases. Actually, this question is originally from Spivak's Calculus, Chapter 2, Problem 4. The problem there, I guess, states a wrong formula, thus I've corrected formula by induction on some special cases.
I've tried to prove formula by myself, but no progress at all. I've tried a substitution: letting j = l - k on the RHS of the formula, but really no progress. Can there be any lemma, a one really useful to prove this result? Especially, I'm getting trouble on modifying the double sum. I can't change the summand variable in a rigorous way.
 
Physics news on Phys.org
  • #2
After posting, I've got a result:
[itex](1-x)^{n}(1-x)^{m} = \{ \binom nn x^{0} + \cdots + \binom {n}{l-m} x^{l-m} + \cdots + \binom n0 x^{0} \} \{ \binom m0 x^{0} + \cdots + \binom {m}{l-n} x^{l-n} + \cdots + \binom mm x^{m} \}[/itex]

If you calculate the coefficient of x^{l} of the above by a product-wise, then you get the answer. Is that right?
 

1. What is a coefficient problem involving combination?

A coefficient problem involving combination is a mathematical problem that involves finding the number of ways to select a certain number of elements from a larger set, without regard to the order in which they are selected. This is often represented by the combination formula, nCr = n! / r!(n-r)!, where n is the total number of elements and r is the number of elements being selected.

2. How do I solve a coefficient problem involving combination?

To solve a coefficient problem involving combination, you first need to determine the values of n and r. Then, plug those values into the combination formula and simplify to find the answer. It is also important to remember to use proper order of operations when simplifying the formula.

3. Can coefficient problems involving combination be solved using a calculator?

Yes, coefficient problems involving combination can be solved using a calculator. Most scientific or graphing calculators have a "nCr" function that allows you to easily input the values of n and r and calculate the answer. However, it is still important to understand the formula and how it works in order to accurately interpret the calculator's results.

4. What is the difference between a coefficient problem involving combination and a permutation problem?

The main difference between a coefficient problem involving combination and a permutation problem is that combination problems do not take into account the order in which the elements are selected, while permutation problems do. In other words, for a combination problem, selecting elements A, B, and C is considered the same as selecting elements B, A, and C. In a permutation problem, these would be considered two different outcomes.

5. Can coefficient problems involving combination be used in real-life situations?

Yes, coefficient problems involving combination can be used in real-life situations. For example, they can be used to calculate the number of different combinations of toppings on a pizza or the number of different seating arrangements for a group of people. They can also be used in probability and statistics to determine the likelihood of certain outcomes occurring.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
601
  • Calculus and Beyond Homework Help
Replies
14
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
418
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
Replies
17
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
982
Back
Top