Derangement Intermediate

Problem - 2529

Let $D_n$ be the derangement count, prove:

  • $D_n =n\cdot D_{n−1} +(−1)^n$
  • $D_n = (n−1)\cdot (D_{n−2} +D_{n−1})$

The first relation can be proved by directly applying the formula: $$\begin{align} n\cdot D_{n−1} +(−1)n &= n\cdot(n-1)!\left(\frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}-\cdots + (-1)^{n-1}\frac{1}{(n-1)!}\right)+(−1)^n\\ &=n!\left(\frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}-\cdots + (-1)^{n-1}\frac{1}{(n-1)! + (-1)^n\frac{1}{n!}}\right)\\ &=D_n\end{align}$$

Then the second relation can be proved using the first one: $$(n−1)\cdot (D_{n−2} +D_{n−1})= (n−1)\cdot D_{n−2} +(n−1)\cdot D_{n−1}=D_{n-1} - (-1)^{n-1} + (n-1)D_{n-1}=nD_{n-1}+(-1)^n=D_n$$

report an error