Combinatorial proof of an identity related to Derangements 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.
 A: Suppose we have a derangement of length $N - 1$.  From this derangement, $N-1$ derangements of length $N$ can be constructed$^{[1]}$:


*

*Replace an entry of the derangement with $N$

*Append the replaced value to the end of the list


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]}$:


*

*Replace the fixed point with $N$

*Append the replaced value to the end of the list


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.
