7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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\}$?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – sahimat Sep 18 '14 at 2:40
  • $\begingroup$ I honestly don't see this pattern $\endgroup$ – zagadka314 Feb 11 '16 at 11:22
  • 2
    $\begingroup$ 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. $\endgroup$ – André 3000 Feb 11 '16 at 14:39
  • $\begingroup$ @Quasicoherent why would we need those largest elements? $\endgroup$ – parvin Aug 5 '17 at 17:13
  • $\begingroup$ @parvin I don't understand your question. Could you clarify? Every subset has a largest element, and we are simply organizing our counting by grouping together those subsets with the same largest element. $\endgroup$ – André 3000 Aug 5 '17 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.