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