Combinatorics identity question

Solution 1:

$\binom{n+1}{r+1}$ is of course the number of ways to choose $r+1$ numbers from the set $\{0,1,\ldots,n\}$. Now break those sets into categories according to the smallest number chosen. If $k$ is the smallest number chosen, the remaining $r$ numbers must come from the $(n-k)$-element set $\{k+1,\ldots,n\}$, so there are $\binom{n-k}r$ ways to choose them. The smallest number chosen can be anywhere from $0$ through $n-r$, so

$$\binom{n+1}{r+1}=\sum_{k=0}^{n-r}\binom{n-k}r\;.$$

Finally, categorize the $(r+1)$-element subsets according to their second-smallest elements. Suppose that the second-smallest element of a set is $k$. Then $r-1$ elements must be chosen from the $n-k$ elements in $\{k+1,\ldots,n\}$, and the smallest element must be chosen from the $k$ elements in $\{0,1,\ldots,k-1\}$; these choices can be made in a total of $k\binom{n-k}{r-1}$ ways. The second-smallest element can be anything from $1$ through $n-r+1$, so

$$\binom{n+1}{r+1}=\sum_{k=1}^{n-r+1}k\binom{n-k}{r-1}\;.$$

Solution 2:

This is what they call the Hockey-Stick Identity or the Chu-Shih-Chieh's Identity as I have encountered it in the book Principle and Techniques in Combinatorics by Chen and Koh. You can read about it from here. :)