Solving recurrence relation with non-constant coefficient Need help with this:
$$D_n=(n-1)(D_{n-1}+D_{n-2})$$
$$n\ge2$$
$$D_1=0,D_2=1$$
This is actually recurrence relation of derangement numbers.
 A: Given ${D}(0)=1$ and ${D}(1)=0$, and the recursion $$D_n=(n-1)\big(D_{n-1}+D_{n-2}\big) \tag1$$Subtracting $n{D}(n-1)$ from both sides of $(1)$ yields
$$
{D}(n)-n{D}(n-1)=-({D}(n-1)-(n-1){D}(n-2))\tag{2}
$$
Let$ A_n = D_n - n D_{n-1}$, and the recurrence relation becomes $A_n = - A_{n-1}$.  With $A_0 = 1$, this recurrence is easy to solve, and we get $D_n - n D_{n-1} = A_n = (-1)^n$. Hence :
$$
{D}(n)-n{D}(n-1)=(-1)^n\tag{3}
$$
Dividing both sides of $(3)$ by $n!$ yields
$$
\frac{{D}(n)}{n!}-\frac{{D}(n-1)}{(n-1)!}=\frac{(-1)^n}{n!}\tag{4}
$$
Equation $(4)$ is very simple to solve for $\dfrac{{D}(n)}{n!}$:
$$
\frac{{D}(n)}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}+C\tag{5}
$$
Putting $n=0$ into equation $(5)$ yields that $C=0$. Therefore,

$$
{D}(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!}
$$

A: By setting $D_n = n! E_n$ we get the following recurrence relation for $E_n$:
$$ E_n = \left(1-\frac{1}{n}\right) E_{n-1} + \frac{1}{n} E_{n-2} \tag{1} $$
then by setting $\Delta_n=E_n-E_{n-1}$ we get
$$ \Delta_n = -\frac{1}{n} \Delta_{n-1} \tag{2}$$
from which $\Delta_n = \frac{(-1)^n}{n!}$ and
$$ D_n = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}\tag{3} $$
You may notice that $\sum_{k=0}^{n}\frac{(-1)^k}{k!}$ converges pretty fast to $\frac{1}{e}$, hence $\frac{1}{e}$ is the asymptotic probability that a random element in $S_n$ (for a large $n$) is a derangement.
