Consider the following identity regarding derangements:
Prove that $d(n) = n \cdot d(n-1) + (-1)^n$, where $d(n)$ denotes the number of derangements of the numbers $1, 2, \ldots, n$.
It's easy to prove the identity using the formula $d(n) = n!\sum_{i=0}^n \frac {(-1)^i}{i!}$. But I was trying to prove it using an combinatorial argument. Any suggestions will be helpful.
Thanks in advance.
Suppose we have a derangement of length $N - 1$. From this derangement, $N-1$ derangements of length $N$ can be constructed$^{[1]}$:
Example: $$\{2, 4, 1, 3\} \text{ becomes } \begin{cases} \{\color{blue}5, 4, 1, 3, 2\} \\ \{2, \color{blue}5, 1, 3, 4\} \\ \{2, 4, \color{blue}5, 3, 1\} \\ \{2, 4, 1, \color{blue}5, 3\} \\ \end{cases}$$
This process will never produce 2 equal $n$-length derangements from different $(n-1)$-length derangements$^{[2]}$.
There is exactly 1 other way to create a derangement$^{[3]}$. Call an arrangement a 1-off-derangement if it has exactly 1 fixed point. A $N-1$ length 1-off-derangement can be made into an $N$-length derangement as$^{[4]}$:
Example:
$$\{3, 2, 4, 1\} \text{ becomes } \{3, \color{blue}5, 4, 1, \color{blue}2\}$$
This process also produces unique results$^{[5]}$.
There are $d(n-1) + (-1)^n$ 1-off-derangements of length $n-1$$^{[6]}$. So total is:
$$\begin{align} d(n) &= \underbrace{(n - 1)~d(n-1)}_{\text{From Derangements}} + \underbrace{d(n-1) + (-1)^n}_{\text{From 1-off-derangements}}\\ \\ &= n~d(n-1)+(-1)^n \end{align}$$
[1] Should be obvious from construction
[2] The process is invertible
[3] When you invert the process, see what happens when the input is a $n$-length derangement but the output is $n-1$ length nonderangement. It must have exactly 1 fixed point.
[4] Should be obvious from construction
[5] The process is invertible
[6] Apologies, I'm not entirely sure how to prove this part, I hope someone can help with this detail.