prove that C(r,r)+C(r+1,r).......+C(n,r) =C(n+1,r+1) for r greater than or equal to 0 and r less than or equal?

2 Answers

  • kb
    Lv 7
    9 years ago
    Favorite Answer

    Repeatedly apply the identity C(n,k) = C(n-1, k) + C(n-1, k-1).

    [This is easy to establish by writing out the factorial definition of C(n,k):

    C(n-1, k) + C(n-1, k-1)

    = (n-1)!/ [k! (n-1-k)!] + (n-1)!/[(k-1)! (n-k)!]

    = (n-k) * (n-1)!/ [k! * (n-k)(n-1-k)!] + k * (n-1)!/[k(k-1)! (n-k)!]

    = (n-k) * (n-1)! + k * (n-1)!] / [k! (n-k)!]

    = (n-1)! * [(n-k) + k] / [k! (n-k)!]

    = n!/[k! (n-k)!]

    = C(n,k), as required.]


    So, C(n+1, r+1)

    = C(n, r+1) + C(n, r)

    = [C(n-1, r+1) + C(n-1, r)] + C(n, r)

    = [C(n-2, r+1) + C(n-2, r)] + C(n-1, r) + C(n, r)


    = [C(r+1, r+1) + C(r+1, r)] + C(r+2, r) + ... + C(n, r)

    = C(r, r) + C(r+1, r) + C(r+2, r) + ... + C(n, r).

    I hope this helps!

  • 9 years ago

    First of all, we need a preliminary identity:

    C(n+1,r+1)=C(n,r)+C(n,r+1), …(*)

    for n>r≥0.

    Proof: When we choose r+1 people among n+1 people,

    two cases arise:

    A certain (specific) person is chosen;

    The person mentioned above isn’t chosen.

    How many ways are there, in each case?

    C(n,r) (we may choose (r+1)-1 people among (n+1)-1 people);

    C(n,r+1) (we may choose r+1 people among (n+1)-1 people).

    Using the sum rule, we have the desired conclusion.

    Now, we substitute a_n for C(n,r+1) and b_n for C(n,r).

    Then, we have , by the identity (*),

    a_(n+1)=b_n+a_n. …(**)

    Here, we set a_n=C(n,r+1) if n≥r+1, 0 if n<r+1;

    b_n=C(n,r) if n≥r, 0 if n<r.

    Then, for all nonnegative integer n,r,




    Since a_0=C(0,r+1)=0, we get

    a_(n+1)=C(r,r)+C(r+1,r)+…+C(n,r), which means

    C(n+1,n+1)= =C(r,r)+C(r+1,r)+…+C(n,r). Thus, we are done.

Still have questions? Get your answers by asking now.