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.

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$.
