Show that $C(n,k)$ equals to $ C(n-1,k-1)+C(n-1,k)$

Question

The question asks me to show that $C(n,k) = C(n-1,k-1)+C(n-1,k)$ by expanding out the formulas and using elementary algebra. It seems like the question requires me to use binomial expansion but Im not sure how I get from $C(n,k)$ to $C(n-1,k-1)+C(n-1,k).$ detailed explanation would be greatly appreciated thank you

Answer 1

We have: $$\begin{aligned}{{n-1}\choose {k-1}}+{{n-1}\choose k}&=\frac{(n-1)!}{(n-k)!\cdot (k-1)!}+\frac{(n-1)!}{(n-k-1)!\cdot (k)!}\\&=\frac{(n-1)!}{(n-k-1)!\cdot (k-1)!}\cdot \left(\frac{1}{n-k}+\frac{1}{k}\right)\\&=\frac{n!}{(n-k)!\cdot k!}\\&={n\choose k}\end{aligned}$$

Of course there is also a combinatorics proof for it.

Answer 2

Since $(1+x)^n = (1+x)(1+x)^{n-1}$, we can use the binomial theorem and compare coefficients of $x^k$.

We have $\sum_{i=0}^n \binom{n}{i} x^i = \sum_{i=0}^{n-1} \binom{n-1}{i} x^i(1+x)$, from which we can read off $\binom{n}{k} = \binom{n-1}{k}+ \binom{n-1}{k-1}$.