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.