Elementary combinatorics problem: which answer is the right one? In how many ways can the sequence of the natural numbers from 1 to 10 be ordered if:
1) each sequence starts with $ 1 $
2) the absolute value of the difference of two successive terms in the sequence is less than or equal to $ 2 $
The problem has to be solved by finding a recursive relation, i.e., if $ x_n $ is the number of ways the sequence $ 1,..,n $ can be ordered with the restrictions given above, then I have to find it as a function of the preceding terms. I've found that $ x_n=x_{n-1}+x_{-3} $ for $ n>5 $ and $ x_n=x_{n-1}+x_{n-3}+1 $ for $ n=4, 5$, but my textbook says the answers is the latter for every $ n $.
Which one is right? 
 A: Let $a_1, \ldots, a_n$ be a valid sequence of length $n>1$.
Then $a_\nu=2$ for some $\nu$.
The only possibilities are $\nu=2$, $\nu=3$, and $\nu=n$ (because the only valid neighbours of $2$ are $3,4$ and the only valid neighbours of $1$ are $2,3$). For $n\ge 4$, these three options are mutually exclusive. Therefore we obtain the recursion
$$x_n=x_{n-1}+x_{n-3}+1\qquad\text{for all $n\ge 4$} $$
from the following three claims:
Claim 1. For $n\ge 2$, there are exactly $x_{n-1}$ valid sequences with $\nu=2$.
Proof.
The map 
$$ (\underbrace{a_1}_1,\underbrace{a_2}_2,\ldots,a_n)\mapsto(\underbrace{a_2-1}_1,a_3-1,\ldots,a_n-1)$$
with inverse map 
$$ (\underbrace{b_1}_1,b_2\ldots, b_{n-1})\mapsto(1,\underbrace{b_1+1}_2,b_2+1,\ldots, b_{n-1}+1)$$
is a bijection between the set of valid sequences of length $n$ with $\nu=2$ and valid seqeunces of length $n-1$. $_\square$
Claim 2. For $n\ge 3$, there are exactly $x_{n-3}$ such sequences with $\nu=3$.
Proof.
For such sequences, necessarily $a_2=3$ and then the map 
$$ (a_1,a_2,\ldots,a_n)\mapsto(a_4-3,a_5-3,\ldots,a_n-3)$$
wth inverse map 
$$ (b_1,b_2\ldots, b_{n-3})\mapsto(1,3,2,b_1+3,b_2+3,\ldots, b_{n-3}+3)$$
is a bijection between the set of valid sequences of length $n$ with $\nu=3$ and valid sequences of length $n-3$. $_\square$
Claim 3. For $n\ge 2$ there is exactly one valid sequence with $\nu=n$.
Proof.
This is clear for $n=2$. For $n>2$ we conclude $a_2=3$ so that
$$(a_1,\ldots, a_n)\mapsto (a_n-1,a_{n-1}-1,\ldots, a_2-1)$$
with inverse map 
$$(b_1,\ldots, b_{n-1})\mapsto (1,b_{n-1}+1,b_{n-2}+1,\ldots, b_1+1)$$
is a bijection between valid sequences of length $n$ ending in $2$ and valid sequences of length $n-1$ ending in $2$. $_\square$
