Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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