Prove by induction that the number of derangements of length $n$ is $D_n = (n-1)(D_{n-1}+D_{n-2}), n>2$

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