Derangement formula; proof by induction Proof by induction that
$
d_{n}=nd_{n-1}+(-1)^{n}
$
where $d_{n}$ is number of $n$-element derangements.

Hints
The number of derangements is given by
$$d_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}.$$
To prove your relationship by induction, show that


*

*it is correct for the base case $n=1$, i.e. that $d_1 = 1 d_0 + (-1)^1$ by plugging in.

*it is correct in the inductive step; i.e., assuming that this is true for all $k=1, \ldots n-1$, prove that this is true for $k=n$.


Can you finish this?
