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: Binomial identity

  1. Dec 4, 2007 #1
    1. The problem statement, all variables and given/known data
    Prove that the following binomial identity holds:

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


    3. The attempt at a solution

    One of the methods i've tried is to use induction on the variable n, but while trying this I got stuk on rewriting the binomial coefficients.... can someone give me a hint if I can use another simple binomial identity for this?

    Another thing I have tried to do is to look at the generating function of the left hand side, and then try to rewrite this to a generating function for the right hand side, but that didn't succeed either....

    Can someone point me a little bit in the right direction?
     
  2. jcsd
  3. Dec 4, 2007 #2

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Try finding two ways to count the number of ways you can choose k balls from a box containing n red balls and k-1 red balls.

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