combinatorics – A question involving the permutations of 1,2,…, n and the fibonacci sequence (Kazakstan-2015)


If $nge 4$. Find the amount of permutations $x_1,…,x_n$ of $1,2,…,n$ such that $x_ile x_{i+2}$ for every $1le ile n-2$ and $x_ile x_{i+3}$ for every $1le i le n-3$.

I have written done this questions taking the case of n=1, 2 etc. and have concluded that the result matched that of the Fibonaccia sequence, in other words that $a_n=a_{n-1}+a_{n-2}$ where $a_i$ is the answer for given $n$. However I can not prove it. Could you please explain to me how to prove it and how to think of each step of the solution?