For all positive integers n and k with nk we have the follow

For all positive integers n and k with n>=k, we have the following equality:

nCk+nC(k-1)=(n+1)Ck

Prove the equality using words, not algebra. As a hint, imagine that there are n+1 people, and one of them has already been assigned to be the leader of the group.

Solution

Say we need to select k peple from n+1

so here we adding case in which leader is selected and one in which he is not selected gives the answer.

first select the leader in k. so now we need to select k-1 from remaining n. which gives nCk-1

In second case we don\'t select leader, so now we need to select k from remaining n. Which gives nCk

adding them gives selecting k from n+1 -------> n+1Ck

nCk +nCk-1 = n+1Ck