1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proving Combinatorial identity

  1. Jul 25, 2005 #1
    Hello everyone!

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

    {{n+k-1}\choose{n-1}} = \sum_{i=1}^k {k-1\choose i-1}{n\choose i}\,\, 1\leq k \leq n

    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:
  2. jcsd
  3. Jul 25, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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: Jul 25, 2005
  4. Jul 25, 2005 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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: Jul 25, 2005
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook