Proof of $(n)_k = (n-1)_k + k(n-1)_{k-1}$

Question

I have to prove that this identity $(n)_k = (n-1)_k + k(n-1)_{k-1}$ is valid. I know that $(n)_k = \frac{n!}{(n-k)!}$, where should I look next?

Answer 1

As stated already in the comments, you can use induction to proof this formula (which might be usefull to do once), but as @Misha Lavrov stated, there is a nice combinatorial interpretation of both sides.

Let me proof the formula by telling a story. Suppose you work in a company with $n$ people. The boss needs to select people to fulfill $k$ speficic tasks (assume everyone has the same skill set, so everyone is equally likely to be chosen and equally likely to be assigned any task, but if chosen, only one task is assigned). Cleary he can do this in $(n)_k$ possible ways.

Now let us count this number in another way. You can be either one of these $k$ people, or not. In case the boss does not choose you, there are $n-1$ remaining people for $k$ tasks, which can be assinged in $(n-1)_{k-1}$ ways. In the other case, i.e. you are chosen, you will be assigned to one of the $k$ possible tasks and the other $k-1$ tasks needs to be assigned to $(n-1)$ people, this last chocie can be done in $(n-1)_{k-1}$ possible ways.

In total, the boss has $$ (n)_k = (n-1)_k + k(n-1)_{k-1} $$ ways to distribute the tasks.