Prove that $\binom {n+1} {k} = \binom {n} {k-1} + \binom {n} {k}$
2. You know that $\binom nk=\frac{n!}{(n-k)!k!},$ apply that to the RHS.