• Support PF! Buy your school textbooks, materials and every day products Here!

Problem Related to Binomial Coefficient

  • Thread starter dpa
  • Start date
  • #1
dpa
147
0
Hi All,

Homework Statement



This is algebraic proof of Vandermonde's identity:

I am having some problem understanding how we reached the second last step and more importantly, last steps from revious steps.
attachment.php?attachmentid=51583&stc=1&d=1349525256.png


src::proofwiki.org

I would be grateful if someone would elaborate it clearly.

Homework Equations


Basically none that are relevant to answer my question.


The Attempt at a Solution


I have no idea how we reached the last two steps.

Thank You.
 

Attachments

Last edited:

Answers and Replies

  • #2
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,543
755
Hi All,

Homework Statement



This is algebraic proof of Vandermonde's identity:

I am having some problem understanding how we reached the second last step and more importantly, last steps from revious steps.
attachment.php?attachmentid=51583&stc=1&d=1349525256.png


src::proofwiki.org

I would be grateful if someone would elaborate it clearly.

Homework Equations


Basically none that are relevant to answer my question.


The Attempt at a Solution


I have no idea how we reached the last two steps.

Thank You.
It is no wonder you are having trouble following that. Besides having a typo, it is written very sloppily. You are working on this (in which I have included the limits):$$
\sum_{k=0}^r \binom r k x^k\sum_{m=0}^s \binom s m x^m$$Notice it started with summation over a rectangle in the ##m,k## plane: ##0\le k\le r,\,0\le m\le s##.

In the second sum he makes a change of index from ##m## to ##n## by substituting ##n=m+k## or ##m=n-k##. This gives, including the limits:$$
\sum_{k=0}^r\binom r k x^k\sum_{n=k}^{s+k}\binom s {n-k}x^{n-k}$$Notice that the lower limit on the second sum is ##n=k##, not ##n-k##. That is a typo. Notice that the region of summation is now ##k\le n\le s+k,\, 0\le k \le r##. If you draw that region in the ##n,k## plane you will see it is a parallelogram. And he has ignored the upper limits in the sums.

What he does next is put it all under a double sum and reverse the order of summation. But when you reverse the limits it gets complicated putting the limits on in the other order. You would have to break the region up into two sums. That is probably why he has ignored the upper limits in the writeup. Good luck deciphering the rest of that writeup.
 
  • #3
dpa
147
0
Thank You. That was very very helpful.
 
  • #4
dpa
147
0
My goal actually is simpler. I have to prove
([itex]\stackrel{2n}{k}[/itex])=[itex]\Sigma^{k}_{l=0}[/itex]([itex]\stackrel{n}{l}[/itex])([itex]\stackrel{n}{k-l}[/itex])

I can't properly use latex but hope you can understand it.

I wanted to follow the above pattern to prove it, but if there is a simpler method, that would be helpful.

Thank You.
 
  • #5
Dick
Science Advisor
Homework Helper
26,258
618
My goal actually is simpler. I have to prove
([itex]\stackrel{2n}{k}[/itex])=[itex]\Sigma^{k}_{l=0}[/itex]([itex]\stackrel{n}{l}[/itex])([itex]\stackrel{n}{k-l}[/itex])

I can't properly use latex but hope you can understand it.

I wanted to follow the above pattern to prove it, but if there is a simpler method, that would be helpful.

Thank You.
It's pretty easy to give a combinatorial argument. You want to chose k objects from 2n objects. Split the 2n up into two groups n. Count the number of ways to pick l from the first group and l-k from the other and sum them up.
 
  • #6
dpa
147
0
Hi Dick,

Thank you for your suggestion. I am sorry for not including some point. I am actually looking for algebraic proof.

Thank You.
 

Related Threads on Problem Related to Binomial Coefficient

  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
6
Views
691
Replies
1
Views
641
Replies
7
Views
2K
Replies
3
Views
526
  • Last Post
Replies
4
Views
929
  • Last Post
Replies
5
Views
3K
Replies
3
Views
618
  • Last Post
Replies
19
Views
1K
Replies
1
Views
3K
Top