My question is as follows:
Find a recurrence relation for the number of n-digit ternary $(0,1,2)$ in which no $1$ appears any where to the right of a $2$
If we introduce an auxiliary variable: let $b_n$ be the number of ternary sequences of length $n$ that do not contain a $2$. If a sequence of length $n$ contains a $2$, you can append a $0$ or a $2$; if it does not contain a $2$, you can append a $0$, a $1$, or a $2$. In particular, you can always append a $0$ or a $2$, and if it does not contain a $2$, you can also append a $1$. Thus,
$$a_{n+1}=2a_n+b_n\;.$$
Clearly $b_{n+1}=2b_n$, and in fact it’s not hard to see that $b_n=2^n$: you’re just counting binary strings of length $n$. Thus, $$a_{n+1}=2a_n+2^n\;.$$
Is this the correct recurrence relation?
This is how I would lay out the answer to be super clear:
You can reason that a valid sequence $a_n$ either contains at least one 2 ($c_{n-1}$ of these) and terminates with a 0 or 2, or contains no 2 ($b_{n-1}$ of these) and terminates in a 1,2 or 3. Hence:
$$a_n=2c_{n-1}+3b_{n-1}\, .$$
Of course, a sequence $a_{n-1}$ either has at least one 2 or none:
$$a_{n-1}=c_{n-1}+b_{n-1}\, ,$$
thus
$$a_n=2a_{n-1}+b_{n-1}\, .$$
But $b_{n-1}$ is just a binary sequence length $n-1$, hence $b_{n-1}=2^{n-1}$ and therefore:
$$a_n=2a_{n-1}+2^{n-1}\, .$$
Iterating:
$$a_n=2(2a_{n-2}+2^{n-2})+2^{n-1}=2^2a_{n-2}+2\cdot 2^{n-1}$$ $$a_n=2^2(2a_{n-3}+2^{n-3})+2\cdot 2^{n-1}=2^3a_{n-3}+3\cdot 2^{n-1}$$ $$\vdots$$ $$a_n=2^na_0+n2^{n-1}\, .$$
Using $a_0=1$ we have:
$$a_n=(n+2)2^{n-1}\, .$$
Alternatively you can reason that the sequence $a_n$ either has no 2 in $2^n$ ways or has it's first 2 in position $k$ (for $k=1,2,\ldots,n$ ) with $2^{k-1}$ binary sequences length $k-1$ of 0s and 1s to the left and $2^{n-k}$ binary sequences length $n-k$ of 0s and 2s to the right. So summing over these possibilities:
$$a_n=2^n+\sum_{k=1}^{n}2^{k-1}2^{n-k}=2^n+\sum_{k=1}^{n}2^{n-1}=2^n+n2^{n-1}\, ,$$
giving the same as before.