Number of ternary sequences of length $n$ with the property that $|x_i - x_{i - 1}| = 1$ for each $i$ such that $2 \leq i \leq n$ Question:

Find the number of ternary sequences (each element of the sequence is $0$, $1$, or $2$) of length $n$ such that $|x_i - x_{i - 1}| = 1$ for each $i$ such that $2 \leq i \leq n$. 

My suggestion:
Firstly notice that every second element must be the digit "1".
Lets separate the problem into $2$ classes:
The sequence starts with 1 - The are exactly $\lfloor n/2 \rfloor$ elements that are not "1". For each element we have $2$ possibilities - it's $\lfloor n/2\rfloor^n$
The sequence starts with either 0 or 2 - The are exactly $\lceil n/2 \rceil$ elements that are not "1". For each element we have 2 possibilities - it's $\lceil n/2 \rceil^n$
Sum it up and get:
$2\cdot\lceil n/2 \rceil^n+\lfloor n/2 \rfloor^n$
Is it correct?
 A: Most of your reasoning is correct, but the final result is not.
As you observed, every other element of a ternary sequence of length $n$ with the property that $|x_i - x_{i - 1}| = 1$ for $i = 2, 3, \ldots, n$ is a $1$.  
Case 1:  The sequence begins with $1$.
As you observed, exactly $\lfloor \frac{n}{2} \rfloor$ elements of the sequence are not equal to $1$.  Each such entry can be filled in two ways, with either a $0$ or $2$.  Hence, there are 
$$2^{\lfloor \frac{n}{2} \rfloor}$$
such sequences.
Case 2: The sequence begins with $0$ or $2$.
As you observed, exactly $\lceil \frac{n}{2} \rceil$ elements of the sequence do not have a $1$ in that position.  Each such entry can be filled in two ways, with either a $0$ or $2$.  Hence, there are 
$$2^{\lceil \frac{n}{2} \rceil}$$
such sequences.
Total:  Since the two cases are mutually exclusive and exhaustive, the number of admissible sequences is 
$$2^{\lfloor \frac{n}{2} \rfloor} + 2^{\lceil \frac{n}{2} \rceil}$$ 
A: Let $a_n,b_n,c_n$ be the number of $n$ lenght sequences which start respectively with 0,1,2.
Then we are interested in $d_n = a_n+b_n+c_n$ and we have $a_n = b_{n-1}$ , $b_n = a_{n-1}+c_{n-1}$ and $c_n = b_{n-1}$. Now solve those recurences and youll get an answer.
