Prove that: ${^{n}\mathrm{C}_{k}} = {^{n-1}\mathrm{C}_{k-1}}+{^{n-1}\mathrm{C}_{k}}$

Question

Question asks to prove:

${^{n}\mathrm{C}_{k}} = {^{n-1}\mathrm{C}_{k-1}}+{^{n-1}\mathrm{C}_{k}}$

My Steps:

$$\begin{align*}\frac{(n-1)!}{(n-k-2)!(k-1)!} + \frac{(n-1)!}{(n-k-1)!(k)!} & = \frac{(n-1)!}{(n-k-2)!(k-1)!} + \frac{(n-1)!}{(n-1-k)(n-k-2)!k!}\end{align*}$$

$$\begin{align*}=\frac{(n-1)!}{(n-k-2)!(k-1)!} + \frac{(n-1)!}{(n-1-k)(n-k-2)!k(k-1)!}\end{align*}$$

$$\begin{align*}=\frac{[k(n-1-k)(n-1)!] + (n -1)!}{(n-1-k)(n-k-2)!k(k-1)!}\end{align*}$$

Now I have no clue on how to continue from here. Help please. Thanks!

Answer 1

Let's say a set $A$ has $N$ elements. Pick one element and mark it $x$. The subsets of $A$ of size $k$ come in two mutually exclusive types:

I. Those containing $x$, and II. Those not containing $x$.

To choose a subset of type I, first remove $x$ from $A$, and from the remaining elements (there are $N-1$ of them) pick a subset of size $k-1$. There are $^{N-1}C_{k-1}$ ways to do it.

To choose a subset of type II, remove $x$ from $A$, and from the remaining elements pick a subset of size $k$. There are $^{N-1}C_{k}$ ways to do it.

That covers all $k$-subsets of $A$, so we are done.