= Solution
The initial values of the two <sequences> agree: $c_0=d_0=1$ and $c_1=-1+c_0=0=d_1$. For $n\geq2$, use the first-order <recurrence relation> at $n$ and $n-1$:
$$
\begin{aligned}
c_n-(n-1)(c_{n-1}+c_{n-2})
&=(-1)^n+c_{n-1}-(n-1)c_{n-2}\\
&=(-1)^n+(-1)^{n-1}=0.
\end{aligned}
$$
Therefore $c_n$ satisfies exactly the same <derangement recurrence> as $d_n$. By <strong induction>, equality of the preceding two terms implies equality of the next term. Consequently
$$
\boxed{c_n=d_n\quad\text{for every }n\geq0.}
$$
The first-order <recurrence relation> therefore also counts <derangements>.
Back to article page
