Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any 2.
$a_1=3$ and $a_2=8$
I am having trouble creating the recurrence relation as well as evaluating.
My thought for the relation is: $a_{n+1}=2a_n+2^n$ or $a_n=2a_{n-1}+2^{n-1}$
We interpret "to the right" as meaning immediately to the right.
Let $b_n$ be the number of "good" strings that do not end in $2$, and let $c_n$ be the number of good strings that end in $2$.
We can see that $b_{n+1}=2b_n+c_n$. For we append a $0$ or a $1$ to a good string that does not end in $2$, or a $0$ to a good string that ends in $2$.
Note that $b_n+c_n=a_n$. So $b_{n+1}=b_n+a_n$ and $c_{n+1}=a_n$.
From $c_{n+1}=a_n$ we get $a_{n+1}-b_{n+1}=a_n$. Thus $$b_{n+1}=a_{n+1}-a_n \quad\text{and therefore } \quad b_{n}=a_{n}=a_{n-1}.$$ Now substitute in $b_{n+1}=b_n+a_n$. We get $$a_{n+1}=a_n=a_n-a+{n-1}+a_n,$$ which simplifies to $$a_{n+1}=3a_n-a_{n-1}.$$ We can solve this with any of the standard methods, for example by finding the zeros of the characteristic polynomial.
Another way: Apart from the unfortunate restriction about $1$ not following $2$, we would have $a_{n+1}=3a_n$. How much does $3a_n$ overcount? It overcounts by including in the count the bad strings where we append a $21$ to a good string of length $n-1$. So, instantly we get $$a_{n+1}=3a_n-a_{n-1}.$$
Remark: In hindsight the problem is trivial. I wrote it up the way I did because in fact I first did it the clumsy way, a matrix version of the first approach.
