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

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?

Answer 1

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.

Answer 2

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}$$