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


    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