Prove by induction that the number of derangements of length $n$ is $D_n = (n-1)(D_{n-1}+D_{n-2}), n>2$ Prove by induction that 
$$
D_n = (n-1)(D_{n-1}+D_{n-2}), n>2
$$
where $D_n$ is the number of derangements of $n$ objects.
I am a little rusty in induction, and here's what I have done so far.
Basis step:  This is easy to prove and trivial, it works for $n=3$ and this is the basis step.
Induction step: Suppose the formula holds for $n$. I will use the relation:
\begin{equation}
D_n = nD_{n-1} + (-1)^n, n\ge2
\label{u28.eq.1}
\tag{i}
\end{equation}
which I know is true because I have proved it before. So
$$
D_{n+1} = (n+1)D_n + (-1)^{n+1}
=(n+1)D_n-(-1)^n
$$
I use again formula \eqref{u28.eq.1} for $(-1)^n$ and obtain
$$
(n+1)D_n-D_n+nD_{n-1} = n(D_n+D_{n-1}),
$$
which is of course what I wanted to prove. The thing is that I didn't use the induction step and I think I am wrong at some step, but I cannot tell where.
 A: Here is an induction argument to complement your method:
Let $P(n)$ be the statement that $D_n = (n - 1)(D_{n - 1} + D_{n - 2})$, where $D_n$ represents the number of derangements of $n$ objects.
Observe that $D_1 = 0$ since there is only one available place and that $D_2 = 1$ since the only derangement involves switching the order of the objects.  
Let $n = 3$.  Consider the sequence $\{1, 2, 3\}$.  The derangements of this sequence are the sequences $\{2, 3, 1\}$ and $\{3, 1, 2\}$.  All other permutations leave at least one of the numbers in its original position.  Hence, $D_3 = 2$.  Observe that 
$$D_3 = 2 = 2(1 + 0) = (3 - 1)(D_2 - D_1)$$
Hence, $P(3)$ holds.
Let's look at the derangements of $\{1, 2, 3, 4\}$.  They are 
\begin{align*}
&\{2,1,4,3\}\\
&\color{blue}{\{2,3,4,1\}}\\
&\color{blue}{\{2,4,1,3\}}\\
&\color{green}{\{3,1,4,2\}}\\
&\{3,4,1,2\}\\
&\color{green}{\{3,4,2,1\}}\\
&\color{green}{\{4,1,2,3\}}\\
&\color{blue}{\{4,3,1,2\}}\\
&\{4,3,2,1\}
\end{align*}
Observe that the derangements shown in blue are produced by appending $4$ to the end of the derangement $\{2, 3, 1\}$ of the sequence $\{1, 2, 3\}$ to obtain the sequence $\{2, 3, 1, 4\}$, then swapping the position of $4$ with one of the other elements in the sequence $\{2, 3, 1, 4\}$.  The derangements shown in green are produced by appending $4$ to the end of the derangement $\{3, 1, 2\}$ of the sequence $\{1, 2, 3\}$ to obtain $\{3, 1, 2, 4\}$, then swapping the position of $4$ with one of the other elements in the sequence $\{3, 1, 2, 4\}$.  
The other three derangements of the sequence $\{1, 2, 3, 4\}$ do not involve making such a swap.  Instead, we choose one of the first three elements, say $k$, to take the fourth position, then derange the remaining three elements.  There are $D_3$ such options since each of the remaining elements is excluded from one of the first $3$ positions as $4$ cannot be placed in the $k$th position (since it is not swapped with $k$) and $j$ cannot be placed in the $j$th position for $j \neq k, 4$.
Observe also that $D_4 = 9 = 3(2 + 1) = (4 - 1)(D_3 + D_2)$, so $P(4)$ holds. 
Assume $P(m)$ holds for each integer $n \leq m$, where $m \geq 3$.  
We wish to count the number of derangements of the sequence $\{1, 2, 3, \ldots, m, m + 1\}$.  In any such derangement, the element $m + 1$ either swaps places with another element or it does not.  
If $m + 1$ does swap places with another element, a derangement of the sequence $\{1, 2, 3, \ldots, m, m + 1\}$ is formed by swapping the place of $m + 1$ and one of the other $m$ elements of the sequence and then deranging the remaining $m - 1$ elements.  There are $mD_{m - 1}$ such derangements.
If $m + 1$ does not swap places with another element, a derangement of the sequence $\{1, 2, 3, \ldots, m, m + 1\}$ is formed by choosing which of the first $m$ elements, say $k$, will occupy position $m + 1$, then deranging the remaining $m$ elements.  There are $D_m$ such choices since one of the first $m$ positions is excluded for each of the $m$ remaining elements as $m + 1$ cannot fill the $k$th position (otherwise it would be a swap) and $j$ cannot fill the $j$th position for $j \neq k, m + 1$. Hence, there are $mD_m$ such derangements that do not involve a swap of $m + 1$ with one of the first $m$ elements.  
Hence, 
$$D_{m + 1} = mD_m + mD_{m - 1} = m(D_m + D_{m - 1})$$ 
so $P(m + 1)$ holds.  Thus, $P(n)$ holds for each $n > 2$.
