 Solution

The initial values are $d_1=0$ and $d_2=1$: one element cannot move, while two elements must be swapped.

For $n\ge 3$, fix one distinguished element, called $n$, and choose its image $j\ne n$, in $n-1$ ways. If $n,j$ form a two-cycle, deleting them leaves an arbitrary derangement on the other $n-2$ elements, giving $d_{n-2}$ choices.

Otherwise the permutation cycle containing $n$ has length at least three. Remove $n$ from that cycle, joining its predecessor directly to $j$. No fixed point is created because the predecessor is not $j$. This gives a derangement on $n-1$ elements. Conversely, any such derangement uniquely recovers the original one by inserting $n$ immediately before $j$ in its cycle. This case contributes $d_{n-1}$ choices for each $j$.

The two cases are disjoint and exhaustive, so the derangement recurrence is