SOLUTION: prove that C(n,r) + C(n-1,r) + C(n-2, r) +.......+ C(r,r) = C(n+1,r+1)

Algebra ->  Permutations -> SOLUTION: prove that C(n,r) + C(n-1,r) + C(n-2, r) +.......+ C(r,r) = C(n+1,r+1)      Log On


   

Question 1045685: prove that C(n,r) + C(n-1,r) + C(n-2, r) +.......+ C(r,r) = C(n+1,r+1)
Answer by robertb(5830) About Me  (Show Source):
You can put this solution on YOUR website!
Proceed by induction: Consider the expression C%28r%2Bk%2Cr%29+%2B+C%28r%2Bk-1%2Cr%29 + ... + +C%28r%2B1%2Cr%29+%2B+C%28r%2Cr%29
For k = 1: C%28r%2B1%2Cr%29+%2B+C%28r%2Cr%29+=+%28r%2B1%29+%2B1+=+r%2B2+=+C%28r%2B2%2Cr%2B1%29, and the relation is true.
Suppose the relation is also true up to k = n - r, so that
C%28n%2Cr%29+%2B+C%28n-1%2Cr%29 + ... + C%28r%2B2%2Cr%29+%2B+C%28r%2B1%2Cr%29+%2B+C%28r%2Cr%29+=+C%28n%2B1%2Cr%2B1%29.
===> C%28n%2B1%2Cr%29+%2B+C%28n%2Cr%29+%2B+C%28n-1%2Cr%29 + ... + +C%28r%2B2%2Cr%29+%2B+C%28r%2B1%2Cr%29+%2B+C%28r%2Cr%29+
= +C%28n%2B1%2Cr%29+%2B+C%28n%2B1%2Cr%2B1%29
= C%28n%2B2%2C+r%2B1%29, by a direct application of Pascal's Triangle C%28N%2CR%29+%2B+C%28N%2CR-1%29+=+C%28N%2B1%2CR%29.
Hence C%28n%2B1%2Cr%29+%2B+C%28n%2Cr%29+%2B+C%28n-1%2Cr%29++ ... + C%28r%2B2%2Cr%29+%2B+C%28r%2B1%2Cr%29+%2B+C%28r%2Cr%29+%0D%0A%0D%0A=+C%28n%2B2%2C+r%2B1%29,
and the relation is proved.