How many words with $N$-characters can be formed from the numbers $\{0, 1, 2\}$, such that adjacent numbers have maximum difference $1$? Example: For $N = 2$ there are $7$ words that can be formed: $<0,0>;<0,1>;<1,0>; <1,1>; <1,2>; <2,1>; <2,2>$. The $<>$ notation specifies a single word. If $N = 10$, how many words can be formed?
a. 8119
b. 8121
c. 8123
d. 8125
e. 8127
I have tried to answer this problem by counting all possible words, then subtracting those words that violate the rules, but I found the answer isn't one of the choices.
$<a, b, c, d, e, f, g, h, i, j>$
All combination is $3^{10} = 59049$
when the difference is more than $1$ then the only possibility is that the word contains a $0$ and a $2$ that are adjacent to each other.
Please help me THANK YOU!
Hint. Let $a_N$, $b_N$ and $c_N$ be the number of $N$-character strings that can be formed from $\{0,1,2\}$, such that adjacent numbers have the maximum difference $1$ and it ends with $0$, $1$, and $2$ respectively. Moreover let $s_N=a_N+b_N+c_N$ be the total number of such $N$-character strings. Then, for $N\geq 1$, they satisfy the recurrences $$\begin{cases} a_{N+1}=a_N+b_N &\text{(before the ending $0$ there is $0$ or $1$)}\\ b_{N+1}=a_N+b_N+c_N=s_N &\text{(before the ending $1$ there is $0$, $1$ or $2$)}\\ c_{N+1}=b_N+c_N &\text{(before the ending $2$ there is $1$ or $2$)} \end{cases}$$ Hence, by taking the sum of these three recurrences, we find $$s_{N+1}=2s_N+b_N=2s_N+s_{N-1}.$$ Now $s_1=3$ and $s_2=7$ (see your remark). Can you take it from here and find $s_{10}$?