We are given the recurrence system $$a_{n+1}=3a_n+1,\\a_0=1.$$ Preliminary observations: Its difference equation is a first-order linear recurrence relation, which generates a sequence in which the consecutive differences between consecutive terms have a common ratio, i.e., the difference between consecutive terms is successively multiplied by a common ratio. (In our example the common ratio is $3$.) Arithmetic and geometric sequences are actually special cases of such a sequence.
We can derive its closed form (general term) using the formula for geometric series:
$$a_0=1\\
a_1=3+1\\
a_2=3^2+3+1\\
a_3=3^3+3^2+3+1\\
a_4=3^4+3^3+3^2+3+1\\
\cdots\\
a_n=3^n+\frac{1(3^n-1)}{3-1}\\
=\frac123^{n+1}-\frac12\quad(n\geq0).$$
In general, when $r\neq1,$ the recurrence relation $a_{n+1}=ra_n+d$ has closed form $$a_n=a_0r^n+\frac{d(r^n-1)}{r-1}\quad(n\geq0).$$ Since this is of the form $$a_n=\alpha r^n+\beta,\tag{*}$$ once a sequence has been identified as such, we can simply plug $n=0,1$ into $(\text*)$ to form a pair of simultaneous linear equations then solve for $\alpha$ and $\beta.$
For $n=3$ we have the good strings $$\{210,211,212,000,001,002,010,011,012,021,100,101,102,110,111,112,121\}$$
So $a_3=17$, not $3\times 7-2\times 3=15$ as you claim.
I would argue: For $n>2$, a good string of length $n$ can begin with $0$ or $1$ and then end with any good word of length $n-1$. Or it can begin with $21$ followed by any good word of length $n-2$. Thus $$a_n=2a_{n-1}+a_{n-2}$$
Note that this gives $a_3=17$ as desired.
Similarly, for the first part, I see $A_3=22$ as we have the good strings $$\{000,001,002,010,011,012,020,021,100,101,102,110,111,112,120,121,200,201,202,210,211,212\}$$
Whereas your formula gives $21$. The reasoning as above yields $A_n=2(A_{n-1}+A_{n-2})$.
(side note: I strongly recommend not using the same variables to denote different things. Here, you used $a_n$ in both parts. I switched the first part to $A_n$ to avoid the confusion).
Best Answer
I made a spreadsheet, calculating $a_n$ further than you did, and saw a pattern,
where $a_n$ became close to powers of $2$.
I then made an additional column with the difference between $a_n$ and $2^{n+1}$
and saw a further obvious pattern there.
That led me to hypothesize that $a_n=2^{n+1}-n$, which I then easily proved by induction.