Find a recurrent function for the solution of... We call a permutation $a_1a_2a_3 \dots a_n$ of numbers $1,2,\dots n$ nice if $|a_i-i| \le 2$ for any $1 \le i \le n$.Then find a recurrent function for $b_n$(solutions for $n$ numbers).
The proof is simple we just have to make a a set of recurrent functions.The book wrote that if we call $c_n$ the number of nice permutations that $a_n=n-1$,$c_n$ is also the number of nice permutations that $a_{n-1}=n$ but it didn't write  a reason.Can you explain that to me?
 A: Let $\pi\colon [n] \to [n]$ be a substitution such that $a_i = \pi(i)$ for all $i$ between $1$ and $n$. If substitution $\pi$ gives a nice permutation of $1, \ldots, n$ then substitution $\pi^{-1}$ also give a nice permutation, because $\pi^{-1}(a_i) = i$ and therefore $|j - \pi^{-1}(j)| = |a_{\pi^{-1}(j)} - \pi^{-1}(a_{\pi^{-1}(j)})| = |a_{\pi^{-1}(j)} - \pi^{-1}(j)| \le 2$ for all $j$ between $1$ and $n$. Let call such substitutions nice too.
The number of nice substitutions $\pi$ with $\pi(n) = n - 1$ is the same as the number of nice substitutions $\pi^{-1}$ with $\pi^{-1}(n - 1) = n$. And this is the answer to your question.

(Here the same idea is written with another words.) Let permutation $a_1, a_2, \ldots, a_n$ of $1, 2, \ldots, n$ be nice. It is easy to see that there is another permutation $p_1, p_2, \ldots, p_n$ of the same numbers such that $p_{a_i} = i$ for all $i$ between $1$ and $n$. This second permutation is also nice because $|p_{a_i} - a_i| = |i - a_i| \le 2$ for all $i$ between $1$ and $n$. And this map from permutation $a_1, \ldots, a_n$ to permutation $p_1, \ldots, p_n$ is one-to-one (bijective). This means that there is equal number of permutations $a_1, \ldots, a_n$ and permutations $p_1, \ldots, p_n$. Also $a_n = n - 1$ if and only if $p_{n - 1} = n$. These observations imply that the number of nice permutations with $a_n = n - 1$ is equal to the number of nice permutations with $a_{n - 1} = n$.
