Proving some identities in Derangements. Let $D_n$ denote the number of derangements of {1,2,3,...,n}.
We know that for $n\geq1$, we have:
\begin{equation*}
D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}+...+(-1)^n\frac{1}{n!}).
\end{equation*}
Given $D_n=nD_{n-1}+(-1)^n$ for $n=2,3,...$
My question is: How can I prove the formula for $D_n$ above using the formula given. I am planning to use induction but I cant proceed. Thanks for your help.
 A: Here is a way to obtain the formula. Assume that
$$
D_n=nD_{n-1}+(-1)^n,\quad n\geq1. \tag1
$$ Dividing $(1)$ by $n!$ gives
$$
\frac{D_n}{n!}=\frac{nD_{n-1}}{n!}+\frac{(-1)^n}{n!},\quad n\geq1,
$$ or
$$
\frac{D_n}{n!}-\frac{D_{n-1}}{(n-1)!}=\frac{(-1)^n}{n!},\quad n\geq1, \tag2
$$ then summing from $n=1$ to $n=N$ we get, by telescoping on the left hand side:
$$
\frac{D_N}{N!}-\frac{D_{0}}{0!}=\sum_{n=1}^N\frac{(-1)^n}{n!},
$$ or

$$
D_N=N!\sum_{n=0}^N\frac{(-1)^n}{n!}, \quad N\geq0,
$$ 

as wanted.
A: You can use induction by considering:
$ X_n=\frac{D_n}{n!}$
so that the given formula can be written as:
$$X_{n}=X_{n-1}+\frac{(-1)^n}{n!} \tag 1$$


*

*Basis step :$X_0=1$

*Induction step assume that $X_{n-1}=1-\frac{1}{1!}-\frac{1}{2!}+\cdots +\frac{(-1)^{n-1}}{(n-1)!}$ hence :
$$X_n=X_{n-1}+\frac{(-1)^n}{n!}=1-\frac{1}{1!}-\frac1{2!}+\cdots +\frac{(-1)^{n-1}}{(n-1)!}+\frac{(-1)^n}{n!}\tag 2 $$


which terminates the proof.
A: This is essentially shown at the end of this answer. I will extract the relevant portion here:

Derivation of the Closed Form from the Recursion:
Given $\mathcal{D}(0)=1$ and $\mathcal{D}(1)=0$, and the recursion
  $$
\mathcal{D}(n)-n\mathcal{D}(n-1)=(-1)^n\tag{1}
$$
  Dividing both sides of $(1)$ by $n!$ yields
  $$
\frac{\mathcal{D}(n)}{n!}-\frac{\mathcal{D}(n-1)}{(n-1)!}=\frac{(-1)^n}{n!}\tag{2}
$$
  Equation $(2)$ is very simple to solve for $\frac{\mathcal{D}(n)}{n!}$:
  $$
\frac{\mathcal{D}(n)}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}+C\tag{3}
$$
  Plugging $n=0$ into equation $(3)$ yields that $C=0$. Therefore,
  $$
\mathcal{D}(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\tag{4}
$$

