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.
 A: 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?
A: Do the derangements of the first $n-1$ elements (from $1$ to $n-1$) and swap one of them ($x$) with $n$. Note that $n$ will never be in the original position of $x$, so we need to add that case. First case: $(n-1)d_{n-1}$ (there are $n-1$ possible choices of $x$ and $d_{n-1}$ derangements). Second case: $(n-1)d_{n-2}$ (same thing, but without $x$ and $n$ there are $d_{n-2}$ derangements). Use the recursion formula do add both cases:
$$\begin{align}
d_{n-1} &= (n-1)d_{n-2}+(-1)^{n-1}\\
d_{n-2} &= \frac{1}{n-1}\left[d_{n-1}+(-1)^n\right]\\
d_{n} &= (n-1)d_{n-1}+(n-1)d_{n-2}\\
 & = (n-1)d_{n-1}+\frac{n-1}{n-1}\left[d_{n-1}+(-1)^n\right]\\
 &= nd_{n-1}+(-1)^n
\end{align}$$
Finally, just show that the recursion formula works for the initial cases $d_0 = 0$ and $d_1 = 1$.
