# 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.

Any help please?

Edit: I managed to solve it after correcting my mistake. Thanks :)

• 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
• @JoséCarlosSantos Oh yes, let me attempt on solving it again. – Little Rookie Nov 24 '17 at 7:34
• For more about this sum see for example this thread. – Raymond Manzoni Nov 24 '17 at 7:35

## 1 Answer

\begin{eqnarray*} l \cdot (D_l + D_{l-1}) &=&\color{red}{l (l)!} \sum_{k=0}^{l}\dfrac{(-1)^k}{k!} + l!\cdot \sum_{k=0}^{l-1}\dfrac{(-1)^k}{k!} \\ &=&(l+1) (l)! \sum_{k=0}^{l-1}\dfrac{(-1)^k}{k!} + \dfrac{(-1)^l l l!}{l!} \\ &=&(l+1) ! \sum_{k=0}^{l-1}\dfrac{(-1)^k}{k!} + \dfrac{(-1)^l (l+1)l!}{ l!}- \dfrac{(-1)^l l!}{l!} \\ &=&(l+1)! \sum_{k=0}^{l+1}\dfrac{(-1)^k}{k!} = \color{blue}{D_{l+1}}. \\ \end{eqnarray*}

• I have managed to solve it after correcting my mistake. Thanks for the help anyway. – Little Rookie Nov 24 '17 at 8:32