Recursion problem - ternary words not containing 121 
How many ternary words in seven letters do not contain the word $121$?

My naive approach is:


*

*If starts with 2 or 3, move to $T(n-1)$

*If starts with 12, move to $T(n-3)$

*If starts with 13, move to $T(n-2)$


But what if we start with $11$? I've seen some techniques using two recursive sequences...
 A: Let's do it recursively, for all lengths $n$.
We let $T_n$ be the number of "good" words of length $n$.
Let $A_n$ be the number that of good words of length $n$ that end in $12$.
Let $B_n$ be the number that of good words of length $n$ that end in $1$.
Let $C_n$ be the number that of good words of length $n$ that end in anything other than $1$ or $12$.
Of course $$T_n=A_n+B_n+ C_n$$
We note that $$A_n=B_{n-1}\quad B_n=B_{n-1}+C_{n-1}\quad C_n=2A_{n-1}+B_{n-1}+2C_{n-
1}=2T_{n-1}-B_{n-1}$$  As we clearly have $$A_1=0\quad B_1=1\quad C_1=2$$ this is easy to implement .  Barring error the first few $T_n$ are $$\{3,9,26,75,217,628,1817,5257,15210,\cdots\}$$  In particular $T_7=\fbox {1817}$
Sanity check:  let's compute $T_4$ by hand.  The bad words are $121*$ and $*121$ hence there are $6$ bad words, so $T_4=81-6=75$ as predicted.  Similarly to compute $T_5$ we eliminate $9$ words of the form $121**$, $9$ words of the type $*121*$ and $9$ of the type $**121$, noting that we have eliminated $12121$ twice.  Hence $T_5=3^5-27+1=243-26=217$ as desired.
A: I think these cases cover the complement set:


*

*Words containing $121$ exactly once

*Words containing $121$ twice without overlap, but not $1212121$

*Words containing $12121$, but not $1212121$

*Words containing $1212121$ (this one's easy)


Can you take it from here?
A: Partition strings into 4 types:


*

*(A) Strings containing a 121

*(B) Else, strings ending in 12

*(C) Else, strings ending in 1

*(D) All other strings


Let $M_{i, j}$ be the number of ways a string in state $i$ can transtion into state $j$ by appending a single character.  Example, $M_{B, D}=2$, because xxxx12 can become a (D) type string in two ways: by appending a 2 (xxxx122) or appending a 3 (xxxx123), but not by appending a 1 because xxxx121 is an (A) type string.
Those transitions can be recorded in a matrix:
$$M = \left[
\begin{array} {r|cccc}
& A & B & C & D \\
\hline
A & 3 & 0 & 0 & 0 \\
B & 1 & 0 & 0 & 2 \\
C & 0 & 1 & 1 & 1 \\
D & 0 & 0 & 1 & 2 \\
\end{array}
\right]$$
The number of transitions over 7 characters is $M^7$:
$$M^7 = \left[
\begin{array} {r|cccc}
& A & B & C & D \\
\hline
A & 2187 &   0 &   0 &    0 \\
B &  931 & 134 & 388 &  732 \\
C &  564 & 173 & 501 &  949 \\
D &  370 & 194 & 561 & 1062 \\
\end{array}
\right]$$
The number of strings containing 121 is $M^7{}_{D, A} = 370$; so the number of strings not containing it is $3^7 - 370 = M^7{}_{D, B} + M^7{}_{D, C} + M^7{}_{D, D} = 194 + 561 + 1062 = 1817$.
A: To follow your own approach, let $T_n$ denote ternary words of length $n$ not containing $121$. Let $1_n$ denote ternary words of length $n$ starting with a $1$ not containing $121$. Then
$$
1_n=1_{n-1}+4T_{n-3}+1_{n-2}
$$
since we have words starting with $11$ as $1_{n-1}$, $122,123,132,133$ as $4T_{n-3}$, and $131$ as $1_{n-2}$. Furthermore
$$
T_n=1_n+2T_{n-1}
$$
since we have words starting with $1$ as $1_n$, and $2,3$ as $2T_{n-1}$. Thus we can form the following table:
$$
\begin{array}{|c|c|c|}
\hline
n&1_n&T_n\\
\hline
0&0&1\\
\hline
1&1&3\\
\hline
2&3&9\\
\hline
3&8&26\\
\hline
4&23&75\\
\hline
5&67&217\\
\hline
6&194&628\\
\hline
7&561&1817\\
\hline
\end{array}
$$
which shows the answer to be $T_7=1817$.
Note that the first values for $n=0,1,2$ are seeds that one has to derive manually before the recursion gets going.
A: The DFA method including a Maple implementation was presented at the following MSE link. In the present case we obtain the following session.

> GFNC([[1,2,1]], 3, true);
                                [[1, 2, 1]]

                                Q[], 0, Q[]

                                Q[], 1, Q[1]

                                Q[], 2, Q[]

                                Q[1], 0, Q[]

                               Q[1], 1, Q[1]

                              Q[1], 2, Q[1, 2]

                              Q[1, 2], 0, Q[]

                           Q[1, 2], 1, Q[1, 2, 1]

                              Q[1, 2], 2, Q[]

                         Q[1, 2, 1], 0, Q[1, 2, 1]

                         Q[1, 2, 1], 1, Q[1, 2, 1]

                         Q[1, 2, 1], 2, Q[1, 2, 1]

                                    2
                                   z  + 1
                           - -------------------
                                3    2
                             2 z  - z  + 3 z - 1

> series(%, z=0, 8);
                  2       3       4        5        6         7      8
     1 + 3 z + 9 z  + 26 z  + 75 z  + 217 z  + 628 z  + 1817 z  + O(z )

This confirms the answer being $1817.$ 
A: The coupled recurrence approach you mention goes like this:  Let $T(n)$ be the number of good strings of length $n$.  Let $U(n)$ be the number of good strings that start with $21$. Let $V(n)$ be the number of good strings that start with $1$.  Let $W(n)$ be the number of good strings that start other than $1$ or $21$.  Then $$T(n)=U(n)+V(n)+W(n)\\ U(n)=V(n-1)\\V(n)=T(n-1)-U(n-1)=V(n-1)+W(n-1)\\W(n)=2U(n-1)+2V(n-1)+2W(n-1)$$
You can imagine a column vector of $(U(n),V(n),W(n))^T$ and find the matrix that takes you from $n-1$ to $n$.  Diagonalize the matrix and the eigenvalues are the rates of growth of each eigenvector.
A: For the $n=7$ case, here's an inclusion-exclusion approach that counts the number of words that avoid the five properties that $121$ appears starting in position $1$, $2$, $3$, $4$, or $5$:
$$\binom{5}{0}3^7 - \binom{5}{1}3^{7-3} + \left[3 \cdot 3^{7-6} + 3 \cdot 3^{7-5}\right] - 1 \cdot 3^{7-7} = 2187-405+36-1=1817$$
The two terms in square brackets for the two-property case arise from whether the two $121$ blocks are disjoint or intersect.  The final term corresponds to the only three-property case: $1212121$.
