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

Proving Combinatorial identity

  • Thread starter Pietjuh
  • Start date
Hello everyone!

I'm trying to prove the following identity, but I'm not very lucky in finding the proof: :eek:

[tex]
{{n+k-1}\choose{n-1}} = \sum_{i=1}^k {k-1\choose i-1}{n\choose i}\,\, 1\leq k \leq n
[/tex]

I've tried to interpret this as a combinatorial problem, and I know the left hand side is the number of k-repeatingcombinations (don't really know the english word for it. The dutch word is k-herhalingscombinaties). But how i can transfer this to the sum on the right hand side... :confused:

Can someone help me a bit with this? :smile:
 

matt grime

Science Advisor
Homework Helper
9,394
3
Do it by inductiom, although there is an obvious combinatorial interpretation:

consider a set of n+k-1 objects partitioned as

1,2,..,n | n+1,...,n+k-1

how many ways are there of picking n-1 things from this?

we can pick r fromthe k-1 on the right of the partition and n-1 -r from the ones one the left, thus

[tex] \binom{n+k-1}{n-1} = \sum_{r=0}^{k-1} \binom{k-1}{r}\binom{n}{n-1-r}[/tex]

just reclall that choosing n-1-r from n is the same as choosing r+1 and nor shift the summation so it is indexed by i from 1 to k not r from 0 to k-1
 
Last edited:

Gokul43201

Staff Emeritus
Science Advisor
Gold Member
6,987
14
LHS = C(n+k-1,n-1) = C(n+k-1,k) {using the identity C(n,k) = C(n, n-k)}

This is simply the number of ways of choosing k objects out of n+k-1 objects.

Find an alternative way of doing this same thing. For instance, consider the collection of objects to be consisting of 2 piles. One pile has n objects and the other pile has k-1 objects. Pick up some i objects from the first pile and the remaining k-i objects from the second pile. Calculate the number of ways of doing this and you will see that this is merely a term on the RHS. Sum through all values of i to generate the complete RHS.

Edit : Just saw matt's post...and this is essentially doing the same thing. If you wish read through both and see how they are equivalent.
 
Last edited:

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top