A coefficient problem involving combination

Click For Summary
SUMMARY

The forum discussion centers on the validity of the formula involving combinations and coefficients: \(\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}\). The user confirms the formula holds true for specific cases and references Spivak's Calculus for context. They explore proving the formula through induction and substitution methods but encounter challenges with modifying the double sum. A derived result involving the product of binomials is presented, suggesting a pathway to calculate coefficients.

PREREQUISITES
  • Understanding of combinatorial identities, specifically binomial coefficients.
  • Familiarity with polynomial expansions and generating functions.
  • Knowledge of mathematical induction techniques.
  • Experience with algebraic manipulation of summations.
NEXT STEPS
  • Study the principles of mathematical induction in combinatorial proofs.
  • Learn about generating functions and their applications in combinatorics.
  • Research binomial theorem applications in polynomial expansions.
  • Examine relevant literature on combinatorial identities, particularly works by Spivak and related mathematicians.
USEFUL FOR

This discussion is beneficial for mathematicians, students studying combinatorics, and educators looking to deepen their understanding of binomial coefficients and polynomial identities.

julypraise
Messages
104
Reaction score
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
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?
 

Similar threads

Replies
1
Views
2K
  • · Replies 14 ·
Replies
14
Views
3K
  • · Replies 11 ·
Replies
11
Views
4K
  • · Replies 9 ·
Replies
9
Views
4K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 14 ·
Replies
14
Views
2K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 6 ·
Replies
6
Views
3K