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

Question

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.

Answer 1

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