# How do I solve this combinatorial proof involving factorial (n)_k?

Let $$n$$ and $$k$$ be positive integers with $$n \ge k$$. Give a combinatorial proof that $$n_k = (n-1)_k + k(n-1)_{k-1},$$ where $$n_k$$ is a falling factorial: $$n_k$$ = $$n(n-1)(n-2)\ldots(n-k+1)$$.

I know $$n_k = n \cdot (n-1)_{k-1}$$. For example $$10_4 = 10 \cdot 9_3$$, which equates to: $$10 \cdot 9 \cdot 8 \cdot 7 = 10 \cdot (9 \cdot 8 \cdot 7)$$.

However, I am completely lost on how to extrapolate $$n_k = (n-1)_k + k(n-1)_{k-1}$$ from $$n_k = n \cdot (n-1)_{k-1}$$.

I can work out numerical examples in my head and it makes perfect sense, but I'm missing something and I dont know what it is that I'm missing.

• Hint: Split the $n$ factor into $\left(n-k\right) + k$. – darij grinberg Mar 1 at 3:16

$$n_k$$ represents the number of arrangements of $$n$$ elements in groups of $$k$$ (the order is relevant here). Split those arrangements into two classes: those where one particular element is part of the group and those where this element is not part of the group. The number of the latter is $$(n-1)_k$$ because you choose among the rest. The number of the former is $$k(n-1)_{k-1}$$ because you choose $$k-1$$ among the remaining $$(n-1)$$ and there are $$k$$ possible locations for the fixed element.
I don't know the notation which you have used(I am still new in combinatorics). So I will use simple factorial notation. $$\frac{n!}{(n-k)!}$$
$$=\frac{{((n-k)+k)}\cdot{(n-1)!}}{(n-k)!}$$
$$=\frac{(n-1)!}{(n-k-1)!}+\frac{k(n-1)!}{(n-k)!}$$
$$=(n-1)_k +k(n-1)_{k-1}$$