Prove recurrence relation of Derangement : $D_n = (n-1)(D_{n-2} +D_{n-1})$

Question

Prove recurrence relation of Derangement: $D_n = (n-1)(D_{n-2} +D_{n-1})$

You should use the Definition of Derangement:

$D_n =$ the number of functions $f$ which are onto and one-to-one such that $f : \{1,2,\cdots ,n\} \to \{ 1,2, \cdots ,n \}$ with $f(i) \neq i$.

Answer 1

Clearly, the statement holds for $n = 3$, if we know that $D_1 = 0, D_2 = 1$. Now, using induction, we assume this holds for $n = k$. We need to prove this for $n = k + 1$.

Let $D$ be the set of derangements for $ \{ 1, 2, 3, \dots, n \}$. We shall construct an aribitrary derangement $f$ for $D$. Let us assume that we assign an arbitrary value $i$ to $f(1)$. That is, $f(1) = i$. We have $(n - 1)$ choices for $i$, from $\{2, 3, \dots n\}$.

Now, we can consider the sub-deragements of the set consisting of $D' = \{1, 2, \dots n\} \setminus \{ i \}$. Now, there are two cases: Either we assign $f(i) = 1$, or we assign $f(i) \neq 1$.

Case 1: $f(i) = 1$

In this case, We are solving the problem where there are $n - 2$ numbers in the domain and $n - 2$ numbers in the range, of the form $\{2, 3, \dots, i - 1, i + 1, \dots n\}$. So here, the total number of ways is $D_{n -2}$.

Case 2: $f(i) \neq 1$

This is the same as solving the derangement problem with $n - 1$ numbers, since each number in the set $2, 3, \dots n$ has one forbidden choice from the set $\{ 2, 3, \dots n \}$. So, here the total number of ways is $D_{n -1}$

Hence, the total number of ways is: Number of ways of picking $i$ $\times$ (Case 1 + Case 2) = $(n - 1)\left( D_{n - 1} + D_{n - 2} \right)$

There's some more exposition on wikipedia you may find helpful

Answer 2

Suppose $f : \{1, \ldots, n\} \to \{1, \ldots, n\}$ with $f(j) \ne j$ for all $j$.

Let $i := f(1)$. (How many possibilities are there for $i$?) Two cases can occur.

1. $f(i) = 1$. In this case, $f$ maps $\{1, \ldots, n\} \setminus \{1, i\}$ to itself, so it is a derangement of $n-2$ objects. (How many possibilities are there for $f$ in this case?)
2. $f(i) \ne 1$. In this case, $f$ maps $\{1, \ldots, n\} \setminus \{1\}$ to $\{1, \ldots, n\} \setminus \{i\}$ in such a way that $f(i) \ne 1$ and $f(j) \ne j$ for $j \ne i$, so this restricted function can be viewed as a derangement of $n-1$ objects.