Solving recurrence relation with non-constant coefficient

Question

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.

Answer 1

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!} $$

Answer 2

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.