Call a permutation $a_1, a_2, \ldots, a_n$ of the integers $1, 2, \ldots, n$ quasi-increasing if $a_k \leq a_{k+1} + 2$ for each $1 \leq k \leq n-1$. For example, $53421$ and $14253$ are quasi-increasing permutations of the integers $1$, $2$, $3$, $4$, $5$, but $45123$ is not. Find the number of quasi-increasing permutations of the integers $1$, $2$, $\ldots$, $7$.
Let $F_n$ be the count of quasi-increasing permutation of the integer $1$, $2$, $\cdots$, $n$. Then we have $F_1=1$, $F_2=2$.
Now consider adding number $n$ to a quasi-increasing sequence from $1$ to $(n-1)$. There are only three spots where $n$ can be placed: before $(n-1)$, before $(n-2)$, or at the end. Therefore, we have the recursion when $n > 2$ as $$F_n=3\times F_{n-1}\implies F_n = 2\times 3^{n-2}\implies F_7=\boxed{486}$$