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: Combinatorial Identity

  1. Jun 22, 2005 #1
    Can someone help me how to deal with this identity that i must prove?

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

    I've tried to figure out what the combinatorial meaning of the right hand side is, but I didn't succeed :(
     
  2. jcsd
  3. Jun 22, 2005 #2
    I think it will help to rewrite it in the form:

    [tex]{n + k-1 \choose k} = \sum_{i=1}^k {k-1\choose k - i} {n \choose i}[/tex]
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook