What is the story behind ${n+1 \choose k} = {n \choose k} + {n \choose k-1}$?

Question

By exploring the inductive proof from this question

I came to the point where I did not understand this step:

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

There is a wikipedia article but it does not make much sense to me.

What is the idea behind this "trick"?

Answer 1

The identity just splits the ${n+1 \choose k}$ subsets into two types: those subsets that contain a given element, and those subsets that do not contain this given element.

Let's call the set of $n+1$ elements $S$ and pick one element $x \in S$.

So first, how many subsets of $S$ of size $k$ contain $x$? Well apart from $x$ there are $n$ elements in $S$. Formally, $|S-\{x\}| = n$. We want subsets of size $k$ and we already have $x$ in our subset. Thus we need to pick $k-1$ elements from $S-\{x\}$. Thus the total number of these subsets is ${n \choose {k-1}}$.

Second, how many subsets of $S$ of size $k$ do not contain $x$? Now we need to pick $k$ elements from $S-\{x\}$, which gives ${n \choose k}$ subsets.

All subsets of $S$ of size $k$ either contain $x$ or not, so we have counted all of them, and found that $${n+1 \choose k} = {n \choose k} + {n \choose k-1}.$$

Answer 2

One is choosing $k$ balls out of $n+1$ is same as choosing with those $n+1$ set broken and the other one is due to property of pascal's triangle.

Answer 3

Although the combinatorial proof is definitely the "correct" one, you can also prove Pascal's identity using brute force, by expanding the binomial coefficients: $$ \binom{n}{k} + \binom{n}{k-1} = \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!} = \frac{n!((n-k+1)+k)}{k!(n-k+1)!} = \frac{(n+1)!}{k!(n-k+1)!} = \binom{n+1}{k}. $$

Answer 4

Firstly, $$ {n \choose k} = \frac{n!}{k!(n-k)!}$$ Next, $$ {n \choose k} + {n \choose k-1} = \frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-(k-1))!}$$ which is equal to $$\frac{n\cdot(n-1)...2\cdot1}{(k\cdot(k-1)...2\cdot1)((n-k)\cdot(n-k-1)...2\cdot1)}+\frac{n\cdot(n-1)...2\cdot1}{((k-1)\cdot(k-2)...2\cdot1)((n-k+1)\cdot(n-k)...2\cdot1)}$$ which is equal to $$\frac{n!}{(k-1)!(n-k)!}\Big(\frac{1}{k}+\frac{1}{n-k+1}\Big) = \frac{n!}{(k-1)!(n-k)!}\Big(\frac{(n-k+1)+k}{k(n-k)}\Big)=\frac{n!}{(k-1)!(n-k)!}\Big(\frac{n+1}{k(n-k+1)}\Big)=\frac{(n+1)\cdot n\cdot(n-1)...2\cdot1}{(k\cdot(k-1)...2\cdot1)((n-k+1)\cdot(n-k)...2\cdot1)}=\frac{(n+1)\cdot n\cdot(n-1)...2\cdot1}{(k\cdot(k-1)...2\cdot1)(((n+1)-k)\cdot(n-k)...2\cdot1)}=\frac{(n+1)!}{k!(n+1)-k)!}={(n+1) \choose k}$$

Yuval Filmus' answer came while I was typing out my answer. Just expanded on his solution I guess?