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.
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.
- Anonymous1 decade agoFavorite Answer
- 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
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)
= (m+k)!/[k!m!] + (m+k)!/[(k-1)!(m+1)!]
= [(m+k)!*(m+1) + (m+k)!k]/[k!(m+1)!]
so the formula also holds for n = m+1