0
$\begingroup$

Could someone help me as I am stuck with coming up with a proof for this?

Assume n is the total number of people in a town. Assume k is the number of possible ways to select a chief of the town. So the RHS is saying that there are k ways to choose a chief from n people.

on the LHS, From $i=k$, and $k=n$, it is referring to from k to n, which is the sum of the remaining people in the town who were not selected $(n-k)$, that there is $k-1$ ways to choose from $i-1$ objects. Since $i=k$, i could be the number of ways to possibly select a chief. If one person is chosen from i, who also belongs to $k, k-1$. But how does this lead to $${n \choose k}$$?

$\endgroup$

marked as duplicate by Sil, N. F. Taussig combinatorics Dec 16 '18 at 16:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

Hint: Partition the set of all $k$-element subsets of $[n] = \{ 1, 2, \dots, n \}$ according to their greatest elements.

If you must use a 'real-world' example, consider putting the $n$ townfolk in order—say, by height—and counting the number of ways to choose a committee of $k$ people which will be chaired by the tallest person on the committee. The left-hand side partitions the set of all possible committees according to who will be the committee chair.

$\endgroup$

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