If $n\ge 4$. Find the amount of permutations $x_1,...,x_n$ of $1,2,...,n$ such that $x_i\le x_{i+2}$ for every $1\le i\le n-2$ and $x_i\le x_{i+3}$ for every $1\le 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?
If $n$ is at the last position it satisfies the requirement so you only need the rest to satisfy it $a_{n-1}$, if $n$ is next to last then the last element has to be $n-1$ (try to prove it) so the rest of the sequence has to satisfy the requirements $a_{n-2}$ clearly $n$ can't be anywhere else.