Consider a finite set $S_n$ with $n\ge 2$ elements and denote by $D_n$ the number of derangements of $S_n$.
How to prove by a direct combinatorial proof that
$$D_n= nD_{n-1}+(-1)^n ?$$
I know a proof based on Euler equality
$$D_n = (n-1)(D_{n-1} + D_{n-2})$$
and tried to separate the cases $n$ even and odd... but I’m not able to get a clean proof so far.
I give you a reference to a nice (and short) paper of A. T. Benjamin and J. Ornstein: A bijective proof of a derangement recurrence. Their bijection is based on the number of elements in the cycle of each permutation which contains the smallest element $1$.
The authors note that Richard Stanley points out in his classic text Enumerative Combinatorics that "considerably more work is required to prove such recurrence combinatorially".