I want to prove the following identity

$$r+(r+1)\binom{r}{r-1}+(r+2)\binom{r+1}{r-1}+...+n\binom{n-1}{r-1}=r\binom{n+1}{r+1} \tag{1}$$

I can prove by induction but I want to prove with combinatorics.

I consider number of different $n+1$ people grouping (each person is different ages) with 2 rules that are

  1. $r+1$ people in a group.

  2. the group consist of $1$ head and $r$ members that head must not be the youngest people in group.

I can find number of different is RHS of (1) but I can't find it is equal to LHS of (1).


Start with choosing $r+1$ people of $n+1$ people so I have the $\binom{n+1}{r+1}$ number that is possible.

Then, I choose the head, I can choose only $r$ people in group (ignoring the youngest people).

So, I have RHS.

I can't find the LHS. All help would be appreciated.


Your start is good. You want to choose $r+1$ people of $n+1$, and a head that isn't the youngest of those. Suppose you first choose who is going to be the youngest in your group. Since there are $r$ others in your group, that must be the 1st, 2nd, ... or $(n-r+1)$th youngest overall (so there are enough older people).

If you've chosen the $k$th youngest overall to be the youngest in the group, you now have $n+1-k$ choices for your head (all the older people) and then you have to choose the remaining $r-1$ members of the group from the remaining $n-k$ people who are older than the designated youngest. That should give you the LHS.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.