Proposition Let n ≥ 2. Then

d_{n} = (n − 1)(d_{n−1} + d_{n−2}).  (1)

Proof : Let π be a derangement of the numbers 1, 2, ..., n. There are n − 1 choices for i = π(1). Fix i. Then there are two possibilities :

(A) π(i) = 1. Then π induces a derangement of the numbers 2, 3, ..., i − 1, i + 1, ..., n, so there are d_{n−2} possibilities left for π.

(B) π(i) ≠ 1. Then, identifying 1 and i, we can imagine that π induces a derangement of 2, 3, ..., n, so there are d_{n−1} possibilities left for π.

Thus, once i is fixed, there are in total d_{n−1} + d_{n−2} possible derangements. And since there were n − 1 choices for i, an application of the multiplication principle yields (1).