# 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?

Relevance

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!

• 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,

a_(n+1)-a_0=∑_(k=0)^n▒b_k

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

=C(r,r)+C(r+1,r)+…+C(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.