# 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?