Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and the Yahoo Answers website is now in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

Anonymous
Anonymous asked in Science & MathematicsMathematics · 1 decade ago

Prove the identity Sigma i=0..n C(i+k-1,k-1) = C(n+k,k). C(n,r) denotes n choose r.?

Ive been trying to solve this by using the formula C(n,r) = n!/r!*(n-r)! . Then I apply the general substitutions i.e n = i+k-1 and r = k-1, however the sum doesnt work out. Help would be greatly appreaciated .. thanks in advance.

1 Answer

Relevance
  • Anonymous
    1 decade ago
    Favorite Answer

    By induction

    - first take n = 0

    then we have

    sum (i = 0) = C(k-1,k-1) = 1 = C(k,k)

    so the result is correct for n = 0

    - Suppose the result is correct for n = 0,1,...,m

    we have to prove the result is correct for n = m+1

    now

    sum(i = 0,1,...,m+1) C(i+k-1,k-1)

    = sum (i =0,1,...,m) C(i+k-1,k-1) + C(m+1+k-1,k-1)

    = (induction for the first part)

    = C(m+k,k) + C(m+k,k-1)

    = formulas

    = (m+k)!/[k!m!] + (m+k)!/[(k-1)!(m+1)!]

    = [(m+k)!*(m+1) + (m+k)!k]/[k!(m+1)!]

    =(m+1+k)!/[k!(m+1)!]

    = C(m+1+k,k)

    so the formula also holds for n = m+1

    QED

Still have questions? Get your answers by asking now.