2009/022) Prove that c(r,r)+c(r+1,r)+.....+c(n,r)=c(n+1,r+1)

The right hand side is choosing r+1 objects from n+1 objects,

let us count another way

as we need to chose r+1 objects if we order the numbers from 1 to n+1 and chose r+1 objects the last object shall be in position r+1 to n+1

let last object be in position m ( r+1 <= m <=n + 1)

then we chose r objects from m-1 objects

this can be done in c(m-1,r)

m varies from 1+1 to n+1

so total number of ways = sum c(m-1.,r) m from r+1 to n+ 1

or sum c(m,r) (m from r to n)
= c(r,r) +c(r+1,r)+ c(r+2,r)+ … c(n,r)

As by 2 methods there are 2 results(it has been counted correctly) so both are same and hence

c(r,r) +c(r+1,r)+ c(r+2,r)+ … c(n,r) = c(n+1,r+1)

hence proved