Recurrence Relations with ternary strings Find and solve a recurrence equation for the number gn of ternary strings of
length n that do not contain 102 as a substring.
I am having some trouble finding the recurrence relation for this question. My thinking is that you can set this problem into cases. If the last digit of the ternary string is 0,1,or 2, then there is 3g(n-1) possible cases of length n-1. Then, continue to do the same for the next digits. 
Any help would be appreciated. Thanks!
 A: I am learning this right now...
I find it helpful to think of it this way: 
building from the end of the string, 
___1 = g(n-1) combinations; splits into: 


*

*___11 = g(n-2)

*___01 = g(n-2)

*___21 = g(n-2)


since they are all legal strings, we keep all of them, so you add g(n-1) to your recursion. 

___0 = g(n-1) combinations; splits into:


*

*___00 = g(n-2)

*___10 = g(n-2)

*___20 = g(n-2), All legal: add g(n-1) to recursion


___2 = g(n-1) combinations; splits into:


*

*___02 = g(n-2) combinations; splits into:
   ____002 = g(n-3)
   ____102 = g(n-3) NOT LEGAL
   ____202 = g(n-3)


*___12 = g(n-2)

*___22 = g(n-2)


Summing everything together, you note that 02 contributes: g(n-2) - g(n-3), and, having already established, by virtue of the ternary property, that g(n-1) = 3g(n-2), you get that __2's contribution is g(n-1) - g(n-3).
Summing everything together, you have:
$$
3g(n-1) - g(n-3) = g(n)
$$
And that just makes sense to me, because this is a tree we are talking about...and this explanation unfolds like a breadth first search reinterpreted as a recursion. Super intuitive. 
A: Consider a ‘good’ string of length $n$. If it does not end in $10$, you can append any of the three digits to make a good string of length $n+1$. If it does end in $10$, however, you can only append a $0$ or a $1$. Thus, if $a(n)$ is the number of good strings of length $n$ that end in $10$, we must have
$$g(n+1)=3\big(g(n)-a(n)\big)+2a(n)=3g(n)-a(n)\;.$$
Of course we want to get rid of $a(n)$ in favor of some combination of values of $g$. A good string of length $n$ that ends in $10$ is simply a good string of length $n-2$ with $10$ appended, and any good string of length $n-2$ will work here: appending $10$ to a good string always creates another good string. Thus, $a(n)=\ldots\;$?
