Factorial manipulation with proving P(n,k)

Question

I need to prove that P(n,k)=$k*P(n-1,k-1)+P(n-1,k)$
So far I have:
$$RHS=k*\frac{(n-1)!}{(k-n)!} + \frac{(n-1)!}{(n-1-k)!}$$ $$=k*\frac{(-1+n)!}{(n-k)!}+\frac{(n-1)!(n-k)!}{(n-1-k)!(n-k)!}$$
$$=k*\frac{(-n+1)!+(n-1)!(n-k)}{(n-k)!},$$

and then I don't know what to do.

Answer 1

You don't say what you have to work with. A combinatoric proof is that $P(n,k)$ is the number of $k$ length sequences from a universe of $n$. Pick $k$ of the universe. Each sequence either starts with one of the $k$ or it does not. The first term of the sum accounts for the ones that do, the second term accounts for those that do not.