How Many Permutations of $\{1,\ldots,n\}$ satisfy that $x_iFinding number of permutations $(x_1,...,x_n)$ of $\{1,2,3,...,n\}$ fitting these conditions:
$x_i\lt x_{i+2}$ for $1\le i\le n-2$
$x_i\lt x_{i+3}$ for $1 \le i \le n-3$
$n\ge 4 $
I went through the small cases for quite some time, but I think it's a combinatorial problem using some greater combinatorial functions, thinking how to do it right now
 A: Let the number be $T_n$ 
Now notice that $x_i \lt x_j$ for all $j \gt i+1$ and $x_i \gt x_k$ for all $k \lt i-1$.
The possible spots for $1$ are $1$ and $2$. For $2$ are $1,2,3$.
Thus we get the recurrence
$$T_n  = T_{n-1} + T_{n-2}$$
with the permutation either starting with $1$, or starting with $2,1$.
Since $T_1 = 1$ and $T_2 = 2$, we get the fibonacci numbers.
A: Notice that you can prove that $x_i<x_j$ if $j\geq i+2$. In particular, to prove this you can set up chains of inequalities like:
$$x_i<x_{i+3}<x_{i+5}<x_{i+7}<\ldots$$
$$x_i<x_{i+2}<x_{i+4}<x_{i+6}<\ldots$$
where the first one covers every odd case and the second one covers every even case. A nice corollary of this is, if we choose some $x_i$, then we can show it is greater than $x_j$ for any $j\in [1,i-2]$ - that is, $x_i$ is greater than $i-2$ distinct elements of the set $\{1,\ldots,n\}$ implying that it is at least $i-1$. Making a similar argument by how many elements are greater than $x_i$ establishes that $x_i$ is either $i-1$, $i$, or $i+1$. Thus, every such permutation consists of fixed points, and 2-cycles between adjacent values.
As was noted quite elegantly in a previous answer, this implies that every permutation starts either with $1$, followed by any permutation of $\{2,\ldots,n\}$ subject to the same condition, or that it starts with $(2\,\,1)$ followed by any valid permutation of $\{3,\ldots,n\}$ and that this yields that it will satisfy the same recurrence as the Fibonacci sequence. Given that there is exactly $1$ valid permutation for $n=0$ and $1$ for $n=1$, we get the Fibonacci sequence as we progress.
