Derangement recurrence $D(n) = nD(n-1) + (-1)^n$

Question

I'm wondering how the following recursion for $D(n)$, the derangement of $[n]$ distinct elements, can be proved

$$D(n) = nD(n-1) + (-1)^n$$

---

I see the argument for

$$D(n) = (n-1)(D(n-1) + D(n-2))$$

where we consider the two cases for when an element, say $a$, is sent to the "position" of any of the other $n-1$ element, say $b$. We then have two cases, first when $b$ is sent to $a$, hence the $D(n-2)$. Second when $b$ is sent to somewhere else, hence $D(n-1)$.

But this logic doesn't really work for $D(n) = nD(n-1) + (-1)^n$, can someone provide a proof?

Answer 1

Algebraic proof:

$$D_{n+1} = nD_n + nD_{n-1} = (n+1)D_n - D_n + nD_{n-1}$$

We want to prove that $nD_{n-1} - D_n = (-1)^{n+1}$ for the case $n+1$ in the induction process.

$$nD_{n-1} - D_n = (n-1)D_{n-1} + D_{n-1} - ((n-1)D_{n-1} + (n-1)D_{n-2}) = D_{n-1} - (n-1)D_{n-2}$$

$$D_{n-1} - (n-1)D_{n-2} = D_{n-1} - (n-2)D_{n-2} - D_{n-2}$$ $$=(n-2)D_{n-2} + (n-2)D_{n-3} -(n-2)D_{n-2} - D_{n-2}$$ $$ = (n-2)D_{n-3} - D_{n-2}$$

So we have: $$nD_{n-1} - D_n = D_{n-1} - (n-1)D_{n-2} = (n-2)D_{n-3} - D_{n-2}$$

If we start with $n$ even and using the second equality, we will end up with

$$4D_3 - D_4 = 2D_1 - D_2 = -1$$

If we start with $n$ odd and using the first equality, we will end up with

$$3D_2 - D_3 = D_2 - 2D_1 = +1$$

Answer 2

It's a simple proof by induction from the recurrence you give: $$\begin{eqnarray}D(n) &=& (n-1)(D(n-1) + D(n-2)) \\ &=& nD(n-1) - (D(n-1) - (n-1)D(n-2))\end{eqnarray}$$ So $$\begin{eqnarray}D(n) - nD(n-1) &=& - (D(n-1) - (n-1)D(n-2)) \\ &=& \cdots \\ &=& (-1)^{n-2} (D(2) - 2D(1)) \\ &=& {-1}^n\end{eqnarray}$$

Answer 3

There are indeed some combinatorial / bijective proofs of this result. They are much more involved and clever though.

See for example the proof by Arthur Benjamin, or Remmel, Wilf (cited in Enumerative Combinatorics by Richard Stanley)

https://www.fq.math.ca/Papers1/55-5/BenjaminOrnstein.pdf