Combinatorial Analysis: Fermat's Combinatorial Identity I was looking through practice questions and need some guidance/assistance in Fermat's combinatorial identity. I read through this on the stack exchange, but the question was modified in the latest edition of my book.
The book asks for a combinatorial argument (no computations needed) to establish the identity:
$${n \choose k} = \sum_{i=k}^n {i-1 \choose k-1}   \text{ where }n\ge k$$
Hint given: Consider set of numbers $1$ through $n$, and how many subsets of size $k$ have $i$ as their highest numbered member?
I'm still getting a grasp on the way these arguments work, so any help is greatly appreciated.
 A: 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.
