Combinatorial Analysis: Fermat's Combinatorial Identity

Solution 1:

Here's the first part to get you started. Fix $i \in \{1, \ldots, n\}$. To choose a subset of size $k$ with largest element $i$, we choose $i$, and then we must choose the remaining $k-1$ elements from $\{1, 2, \ldots, i-1\}$. (If we choose an element in the range $\{i+1, i+2, \ldots, n\}$, then $i$ won't be the largest element!)

Can you see where the summation comes from? What are the possible values for the largest element of a $k$-element subset of $\{1, 2, \ldots, n\}$?

Edit. Editing in my comment from below:

We are going to count the number of $k$-element subsets of $\{1,\ldots,n\}$, of which there are $\binom{n}{k}$, ordering them by their largest element. To choose a subset of size $k$ with largest element $i$, we choose $i$, and then we must choose the remaining $k-1$ elements from $\{1,2,\ldots,i−1\}$, which yields $\binom{i-1}{k-1}$ possibilities. Since this is a $k$-element subset, the largest element $i$ must be in the range $\{k,k+1,\ldots,n\}$, so we sum over this range.