How many permutations $\left(a_1,a_2,\dots,a_n \right)$ of $\left(1,2,\dots,n \right)$ such that $$\left|a_{i+1} - a_i \right| \le 2, \ \forall i=1,2,\dots,n-1.$$ At first I thought this might be an induction problem, but the best idea I have had so far is to look at it through recurrent relations. Let the number of valid permutations for $n$ where the last element is $a_n$ be $P_n$. We then know $P_n = P_{n-1} + P_{n-2} + 1$. This can be solved to get $P_n = c_1 F_n + c_2 L_n - 1$ (where $c_1$ and $c_2$ are arbitrary parameters and $F_n$ is the n-th Fibonnaci number and $L_n$ is the n-th Lucas number). However, I am not sure how to solve the other cases with induction or reccurence.
The only answer in the source is that it's a famous problem, but I have not been able to find any other problems that are similiar to it. Any help is appreciated, thanks!
