# Combinatorial proof $\sum_{i=k}^n {i-1 \choose k-1} = {n \choose k}$ [duplicate]

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

## marked as duplicate by Sil, N. F. Taussig combinatorics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Dec 16 '18 at 16:03

• The linked question may help you to obtain an answer, but I think an important prerequisite is to learn how to interpret combinatorial expressions properly. In the quantity $\binom{n}{k}$, the number $k$ is the number being chosen, not the number of ways to choose. The very first thing you need to get straight is that $\binom{n}{k}$ is the number of ways to choose $k$ items out of a set of $n$ items. In the problem of choosing a single chief from a town of $n$ people, the answer would be $\binom{n}{1}$ or $n$. – Will Orrick Dec 16 '18 at 16:18
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.