How can I solve the following exercise (from an exam from previous year):
Let $a_n$ denote the number of cycles $\pi\!=\!(\pi_1,\ldots,\pi_n)\!\in\!S_n$, such that $\pi_i\!+\!1 \neq \pi_{i+1}(\!\!\!\mod n)$ for $i\!=\!1,\ldots,n$. For example, $a_4\!=\!1$, since $(1432)$ is the only such cycle. Compute $a_n$.
My attempt: Let's say that $\pi$ is bad at $i$ if $\pi_i\!+\!1 = \pi_{i+1}(\!\!\!\mod n)$, and it is good if it is not bad at any $i$. Denote $A_n\!:=\!\{\pi\!\in\!S_n; \pi\text{ is good}\}$, so $a_n\!=\!|A_n|$. Each $\pi\!\in\!A_n$ is obtained from either some $\alpha\!\in\!A_{n-1}$ (by inserting $n$ at any of the $n\!-\!1$ places except after $n\!-\!1$ or before $1$, which gives $n\!-\!3$ choices), or from some $\beta\!\in\!B_{n-1}\!:=\!\{\pi\!\in\!S_n; \pi\text{ is bad at precisely one place}\}$ (by inserting $n$ in the middle of the bad place, which gives one choice). Thus for $b_n\!:=\!|B_n|$, we have $a_n=(n\!-\!3)a_{n-1}\!+b_{n-1}.$ Now, what is $b_n$? Each $\pi\!\in\!B_n$ can be transformed so that it is bad at $(\ldots n,1\ldots)$, namely if $\pi$ is bad at $(\ldots\pi_k,\pi_{k+1}\ldots)$, we replace each $\pi_i$ by $\pi_i\!+\!n\!-\!\pi_k (\!\!\!\mod n)$. This transformation sends $n$ different cycles to the same one, which proves $b_n\!=\!na_{n-1}$. Therefore $a_n=(n\!-\!3)a_{n-1}\!+(n\!-\!1)a_{n-2},$ with $a_3\!=\!a_4\!=\!1$. Now I don't know what to do, since this is a linear homogenous difference equation with nonconstant coefficients.
Question: Is this recursion correct? How can I solve the exercise?