I have that $a_n$ is the number of permutations where $i$ is not immediately followed by $i+1$ and: \begin{align*} a_n = \sum_{k=0}^{n-1} (-1)^k (n-k)! \end{align*} Which I obtained using the inclusion exclusion principle.
I am trying to show that $a_n = D_{n} + D_{n-1}$ where $D_n$ is the number of derangements on $[n]$.
Given that \begin{align*} D_n = \sum_{k=0}^n \frac{(-1)^kn!}{k!} \end{align*} I have tried to expand the summation for all terms but i am having trouble showing equality.
Observe that with inclusion-exclusion we can count the number of permutations having at least $k$ values where $q$ is followed by $q+1$ by choosing those $k$ from the range from $1$ to $n-1$ and fusing them with the elements that follow immediately, forming at most $k$ blocks. We may then permute these $n-k$ items any way we like.
This yields per inclusion-exclusion
$$\sum_{k=0}^{n-1} {n-1\choose k} (-1)^k (n-k)! = (n-1)! \sum_{k=0}^{n-1} \frac{(-1)^k}{k!} (n-k) \\ = (n-1)! \sum_{k=0}^{n} \frac{(-1)^k}{k!} (n-k) = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} - (n-1)! \sum_{k=0}^{n} k \frac{(-1)^k}{k!} \\ = D_n - (n-1)! \sum_{k=1}^{n} k \frac{(-1)^k}{k!} = D_n - (n-1)! \sum_{k=1}^{n} \frac{(-1)^k}{(k-1)!} \\ = D_n + (n-1)! \sum_{k=0}^{n-1} \frac{(-1)^k}{k!} = D_n + D_{n-1}.$$
A block of length $m$ reduces the number of items being permuted by $m$ and then adds one back in. On the other hand $m-1$ is the number of adjacent consecutive items in the block and summing this over all blocks yields $k.$
