# How many words with $N$-characters can be formed from the numbers $\{0, 1, 2\}$, such that adjacent numbers have maximum difference 1? [duplicate]

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.

## marked as duplicate by Shailesh, hardmath, Aqua, GNUSupporter 8964民主女神 地下教會, LeucippusDec 20 '17 at 0:06

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}$?
• Because $b_{N+1}=a_N+b_N+c_N$ and $s_N=a_N+b_N+c_N$. – Robert Z Dec 19 '17 at 9:44