The Number of permutations of [n] such that $|\pi(i)-i|\leq 2$ Let $a_n$ be a  number of permutations of the set $[n]$ such that 
$$ |\pi(i)-i|\leq 2$$.
I can obtaine the GFs of these restriction permutations. It is equal 
$$F(z)=\frac{1-z}{1-2z-3z^3+z^5}$$
I know That $a_n$ satisfies in the following recurrence relation
$$a_n=2a_{n-1}+3a_{n-3}-a_{n-5}$$
How can get this recurrence relation? 
Is it combinatorial interpretation for it?
Is it close formula for positive integer $k$ such that
$$|\pi(i)-i|\leq k$$.
 A: Here is a direct derivation of the recurrence.
Let $P_n$ be the set of $\pi:[n]\to[n]$ such that $|\pi(i)-i|\le 2$ for each $i\in[n]$, so that $a_n=|P_n|$.
Let $b_n$ be the number of injections $f:[n]\to[n-1]\cup\{n+1\}$ such that $|f(i)-i|\le 2$ for each $i\in[n]$, and let $c_n$ be the number of injections $f:[n]\to[n-2]\cup\{n,n+1\}$ such that $|f(i)-i|\le 2$ for each $i\in[n]$. If $\pi\in P_n$, then $\pi(n)$ is $n$, $n-1$, or $n-2$. 


*

*If $\pi(n)=n$, then $\pi\upharpoonright[n-1]\in P_{n-1}$; there are $a_{n-1}$ such $\pi\in P_n$.

*If $\pi(n)=n-1$, then $\pi\upharpoonright[n-1]$ is an injection to $[n-2]\cup\{n\}$; there are $b_{n-1}$ such $\pi\in P_n$.

*If $\pi(n)=n-2$, then $\pi\upharpoonright[n-1]$ is an injection to $[n-3]\cup\{n-1,n\}$; there are $c_{n-1}$ of these.


Thus, $a_n=a_{n-1}+b_{n-1}+c_{n-1}$.
Next, suppose that $f:[n]\to[n-1]\cup\{n+1\}$ is an injection such that $|f(i)-i|\le 2$ for each $i\in[n]$; then $f(n)=n+1$, or $f(n-1)=n+1$.


*

*If $f(n)=n+1$, then $f\upharpoonright[n-1]\in P_{n-1}$; there are $a_{n-1}$ such $f$.

*If $f(n-1)=n+1$, then $f^{-1}\upharpoonright[n-1]$ is an injection to $[n-2]\cup\{n\}$; there are $b_{n-1}$ of these.


Thus, $b_n=a_{n-1}+b_{n-1}$.
Now suppose that $f:[n]\to[n-2]\cup\{n,n+1\}$ is an injection such that $|f(i)-i|\le 2$ for each $i\in[n]$; then $f(n)=n+1$, or $f(n-1)=n+1$.


*

*If $f(n)=n+1$, then $f\upharpoonright[n-1]$ is an injection to $[n-2]\cup\{n\}$; there are $b_{n-1}$ of these.

*If $f(n-1)=n+1$, then $f\upharpoonright[n-2]\cup\{n\}$ is a permutation of $[n-2]\cup\{n\}$. Either $f(n)=n$, or $f(n)=n-2$ and $f(n-2)=n$. In the first case $f\upharpoonright[n-2]\in P_{n-2}$, and in the second case $f\upharpoonright[n-3]$, so there are altogether $a_{n-2}+a_{n-3}$ of these.


Thus, $c_n=b_{n-1}+a_{n-2}+a_{n-3}$.
We can now reduce the system of recurrences to a single recurrence:
$$\begin{align*}
a_n&=a_{n-1}+\color{red}{b_{n-1}}+\color{blue}{c_{n-1}}\\
&=a_{n-1}+\color{red}{a_{n-2}+b_{n-2}}+\color{blue}{b_{n-2}+a_{n-3}+a_{n-4}}\\
&=a_{n-1}+a_{n-2}+2b_{n-2}+a_{n-3}+a_{n-4}\\
&=a_{n-1}+\color{green}{(a_{n-2}+b_{n-2}+c_{n-2})}+b_{n-2}+a_{n-3}+a_{n-4}\color{brown}{-c_{n-2}}\\
&=a_{n-1}+\color{green}{a_{n-1}}+\color{purple}{b_{n-2}}+a_{n-3}+a_{n-4}\color{brown}{-b_{n-3}-a_{n-4}-a_{n-5}}\\
&=2a_{n-1}+\color{purple}{(a_{n-3}+b_{n-3})}+a_{n-3}-b_{n-3}-a_{n-5}\\
&=2a_{n-1}+2a_{n-3}-a_{n-5}
\end{align*}$$
