Permutation of $\{1,2,3,\dotsc,n\}$ Define $U_n$ as the number of possible permutation $\{a_1,a_2,\dotsc,a_n\}$ from $\{1,2,\dotsc,n\}$ such that $a_1=1$ and $\mid\ a_{i+1}-a_i\mid\leq2$ for all $i=1,2,\dotsc,n-1.$ Find the remainder of $U_{2017}+U_{2018}$ when devided by $3$.
I am asked to first construct a recursive relation between each term to solve the problem. I cannot think of any way to construct any relation between each term. Help, hint, and solution would be appreciated.
 A: You just have to construct the generating sequence for these $2$-bounded left-anchored permutations (from now on, our permutations), and this article by Gillespie and Monks contains much more. Let $R_n$ be the subset of our partitions in $S_n$ and let $r_n=|R_n|$. We have $r_1=1, r_2=1, r_3=2$ and for any $n\geq 4$ every element of $R_n$ falls into one of these cases

*

*starts with $12$

*starts with $1324$

*starts with $13$ and ends with a $2$
and this leads to the following generating function (OEIS 38718)
$$ \sum_{n\geq 1} r_n x^n = \frac{x-x^2+x^3}{1-2x+x^2-x^3+x^4} $$
which in $\mathbb{F}_3[[x]]$ equals
$$ \frac{x(x+1)^2}{(x-1)(x+1)(x^2-x-1)}=\frac{x(x+1)}{(1-x)(1-x-x^2)}=-\frac{2}{1-x}+\frac{x+2}{1-x-x^2} $$
leading to the congruence
$$ r_n \equiv -2+F_n+2 F_{n+1}\equiv 1-(F_{n+1}-F_n)\equiv 1-F_{n-1} \pmod{3}$$
where $F_n$ is a Fibonacci number. The sequence $\{F_n\pmod{3}\}_{n\geq 0}$ is purely periodic with period $1,1,2,0,2,2,1,0$ (length $8$) and you have all the ingredients to solve the given question and much more.
