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

Question

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

Answer 1

Here is an algebraic proof: We have (exercise) $$\binom{n}k=\binom{n-1}{k}+\binom{n-1}{k-1}$$ for all $n\in\mathbb N$ and $k\in\mathbb N\cap[1,n]$.

So $$\binom{n}k = \binom{n-1}{k-1}+\color{blue}{\binom{n-1}{k}}=\binom{n-1}{k-1}+\color{blue}{\binom{n-2}{k-1}+\binom{n-2}{k}}=\dots=\binom{n-1}{k-1}+\binom{n-2}{k-1}+\dots+\binom{k}{k}.$$

But now we are done because $$\binom{k}{k}=1=\binom{k-1}{k-1}.$$

My proof can be fully formalized using induction.

Answer 2

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.

Answer 3

You basically want to show that, $$ \sum_{i=m}^n {i\choose m} = {{n+1}\choose {m+1}} $$

Consider the set $\{1,2,...,n+1\}$. You want to count how many subsets of size $m+1$ you can choose.

For each $1\leq j\leq (n+1)$, let $N(j)$ denote the subsets of size $m+1$ whose maximum integer is equal to $j$.

Then we would have that, $$ \sum_{j=1}^{m+1} N(j) = {{n+1}\choose {m+1}}$$

It remains to argue that, $$N(j) = {{j-1}\choose m} $$

Therefore, $$ \sum_{j=1}^{m+1} {{j-1}\choose m} = {{n+1}\choose {m+1}} $$

Now substitute $i=j-1$, and the index changes from $i=0$ to $i=m$.

From here your result will follow.

Answer 4

Using the fact that $ \binom{p}{k}=\binom{p-1}{k}+\binom{p-1}{k-1} $, we have : \begin{aligned}\sum_{p=k}^{n}{\binom{p-1}{k-1}}&=\sum_{p=k}^{n}{\left(\binom{p}{k}-\binom{p-1}{k}\right)}\\ &=\binom{n}{k}-\binom{k-1}{k}\\ &=\binom{n}{k}\end{aligned}