Prove that $n! = \sum_{k=0}^n\binom{n}{k}d_k,$ where $d_n$ is the number of derangements of ${1,2,..., n}$.

Question

Prove that $$n! = \sum_{k=0}^n\binom{n}{k}d_k,$$ where $d_n$ is the number of derangements of ${1,2,..., n}$. We know that the number of derangements $d_n$ is given by $$d_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$$ Thus we have $$\sum_{k=0}^n\binom{n}{k}n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$$ We take note that $$e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!}$$ Let $x=-1$ and we see that $$\sum_{k=0}^n\binom{n}{k}n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}=\frac{1}{e}\sum_{k=0}^n\binom{n}{k}n!$$ This is the only way I could think of to simplify the expression, but I do not think it is useful in this proof. Any help would be great!

Answer 1

Hint : Try a combinatorial proof, much easier : a permutation is determined by the choice of its $n-k$ fixed points and the fact that the other $k$ elements are "deranged".