A recurrence relation for the derangements of $n$ distinct objects is given as follows.
$D_n=(n-1) \left (D_{n-1}+D_{n-2} \right )$
The explanation I'm tempted to provide to explain this is the following:
First of all, consider two arbitrary people A and B within the group.
Consider two cases.
Case 1: A picks B's hat, but B does not pick A's hat.
Person A has $n-1$ hats to choose from, leaving a remainder of $n-1$ people to choose their hats, hence the $D_{n-1}$.
Case 2: A picks B's hat, and B picks A's hat.
Person A has $n-1$ ways to choose B's hat (B is arbitrary). B has only one way to choose A's hat. The remaining $n-2$ people now choose their hats hence $D_{n-2}$.
Add the two cases to get the recurrence.
My question is, won't some of the derangements from Case 1 fall into Case 2, hence double counting? In Case 1, we imposed that A must pick B's hat, but did not impose that B must not get A's hat.
What is wrong with my reasoning then? It seems to yield the recurrence, but the potential double counting is a bit problematic.
Consider your Case I as A picks the hat of B $\ne$ A, and B does not pick A's hat. Then to get a derangement, $n-1$ people must choose $n-1$ hats with B not picking A's hat and everyone else not picking his/her own hat, which is equivalent to a derangement of $n-1$.