Proof that ${n \choose k}={k-1 \choose k-1}+{k \choose k-1}+{k+1 \choose k-1}+\cdots+{n-1 \choose k-1}$ [duplicate]

$${n \choose k}={k-1 \choose k-1}+{k \choose k-1}+{k+1 \choose k-1}+\cdots+{n-1 \choose k-1}$$

my attempt:

in the first let's write the relation between ${n \choose k}$ and ${n \choose k-1}$ and for explain my idea, let's do that when $n=6$ and $k=4$

so ${6 \choose 4}$ is the number of ways to choose 4 element from [6],my idea is that we can choose 4 element from [6] by choosing 3 elements from [6] and 1 element from the remaining (3) so it is ${6 \choose 3} .{3 \choose 1}$ but we must to note that they are four similar 4-subset so we must to divise by 4

so the finally expression is that $\frac{{6 \choose 3} .{3 \choose 1}}{4}$

and we can doing the same thing with any $n$ and $k$

so ${n \choose k}=\frac{{n \choose k-1} .{n-(k-1) \choose 1}}{n}$

so now it is enough to show that $\frac{{n \choose k-1} .{n-(k-1) \choose 1}}{n}={k-1 \choose k-1}+{k \choose k-1}+{k+1 \choose k-1}+....+{n-1 \choose k-1}$

now let's return to $\frac{{6 \choose 3} .{3 \choose 1}}{4}$ that is the numbers of different ways to choose 3 people from 6 and 1 from the remaining, we can do that by an other way

this way is choosing 3 element from 3 with an known element element from the remaining ,or choose 3 element from 4 with an other element from the remaining , or choose 3 element from 5 with an other element from the remaining

so that mean :${3 \choose 3}.1+{4 \choose 3}.1+{5 \choose3}.1$

and also we can do that with any k and n , so by same steps we can can prove ${n \choose k}={k-1 \choose k-1}+{k \choose k-1}+{k+1 \choose k-1}+....+{n-1 \choose k-1}$

I think I didn't explain my idea in good way, but maybe the general idea it's clear

so what do you think about it?

Solution 1:

I think this is a tidied-up version of your strategy. To choose $k$ objects from $n$ in a line, put a divider to the left of the last item chosen, and choose $k-1$ of the items left of that divider. Depending on where the divider is placed, the number of items to the left of it is anywhere from $k-1$ to $n-1$; and if there are $m$ items to its left, you have $\binom{m}{k-1}$ options. Therefore, $\binom{n}{k}=\sum_{k-1}^{n-1}\binom{m}{k-1}$, as desired.