# 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.

• – StubbornAtom Feb 19 '18 at 17:48

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\}$?
• We are going to count the number of $k$-element subsets of $\{1, \ldots, n\}$, of which there are $\binom{n}{k}$, in order of 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. – André 3000 Feb 11 '16 at 14:39