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

• Feb 19, 2018 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\}$$?

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.

• Yes, this helps a lot actually. By picking one number smaller at a time, it covers the whole summation, and thus gives me the total n choose k (whatever k is defined as). Thank you for the insight. (I think that's what you were getting at). //side note: I would upvote, but lack the "rep", but will return when I can Sep 18, 2014 at 2:40
• I honestly don't see this pattern
– user251299
Feb 11, 2016 at 11:22
• 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. Feb 11, 2016 at 14:39
• @Quasicoherent why would we need those largest elements? Aug 5, 2017 at 17:13
• @user1234 Did you read my comment above? I've edited it into the answer now. I think this answers your question. Jul 3, 2020 at 20:58