# Prove the equality using complete mathematical induction.

Given that $D_0 = 1, D_1 = 0, D_n = (n-1)(D_{n-1}+D_{n-2})$ for all $n\geq 2$.

Prove the equality $$D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$$

I wish to prove the equalty using Complete Induction.

Let $P(n)$ be the above statement for $n\geq 2$.

Basis Step: $P(0)$ and $P(1)$ are true by the initial conditions.

Inductive step: Let $l\geq 1$ be fixed. Suppose that $P(m)$ is true for all $0\leq m \leq l$.

LHS of $P(l+1) = l \cdot (D_l + D_{l-1}) = (l+1)! \sum_{k=0}^{l}\dfrac{(-1)^k}{k!} + l!\cdot \sum_{k=0}^{l-1}\dfrac{(-1)^k}{k!}$

From there, I have tried to simplify the expression and equate it to the RHS of $P(l+1)$ but I can't get the RHS.

• In your attempt, $(l+1)!$ should be $l.l!$. – José Carlos Santos Nov 24 '17 at 7:27
• In order to give the context of the issue, $D_n$ is a number of "Derangements" of $n$ objects. Googling with this keyword (coming from combinatorics) plus the word "recurrence", you will find many connections. – Jean Marie Nov 24 '17 at 7:32