I found this problem in section $5$ of "A path to combinatorics for undergraduates" from Titu Andreescu, but I don't know what's wrong with my solution.
First I defined $A_n$ to be the set of "good numbers" and $a_n = |A_n|$ (those that satisfy the problem statement). Now we let $B_n \subseteq A_n$ such that $B_n$ consists of the good numbers whose last digit is $1$ and $b_n = |B_n|$.
Now given a $n+1$-digit good number, the first $n$ digits must be a good number; so by taking an $n$-digit good number, if this number is in $B_n$ then we can construct only $2$ good numbers because we cannot add a $1$ to the end. On the other hand if the number isn't in $B_n$ we can add any of the three digits to the end to obtain a $n+1$-digit. So based on this my thought was that we can write the recursion:
$a_n = 2b_n + 3(a_n-b_n) = 3a_n - b_n$
Where $a_1 = 3$ and $a_2 = 8$ (when $n = 2$ the only bad number is $11$). However for the case where $n = 3$ we get $a_n = 3(8)-3 = 21$ but in reality only $111,112,211,113,311$ so the ammount of good numbers is $22$. Can anyone explain to me why my solution is wrong? And how to actually solve the problem? Any help would be appreciated.
Recursive Relation
There is a mistake in your recursive relation. The correct relation should be:
$$ a_{n+1}=3a_{n}-b_{n} $$
This is only one half of the relation. You also need a formula to get $b_{n+1}$. Each number in $B_{n+1}$ is a good number with $n$ digits that does not end with $1$, followed by an extra $1$ at the end. Therefore, we have
$$ b_{n+1}=a_{n}-b_{n} $$
Matrix Form
Common way to solve the problem is using the matrix form:
$$ \begin{Bmatrix} a_{n+1} \\ b_{n+1} \end{Bmatrix} = \begin{bmatrix} 3 & -1 \\ 1 & -1 \end{bmatrix} \begin{Bmatrix} a_{n} \\ b_{n} \end{Bmatrix} $$
Equivalently,
$$ \begin{Bmatrix} a_{n} \\ b_{n} \end{Bmatrix} = \begin{bmatrix} 3 & -1 \\ 1 & -1 \end{bmatrix}^{n-1} \begin{Bmatrix} a_{1} \\ b_{1} \end{Bmatrix} $$
Eigenvalues and Eigenvectors
The eigenvalue - eigenvector pairs of the square matrix are:
$$ \begin{aligned} \lambda_{1}=1+\sqrt{3},&\phantom{x}\mathbf{v}_{1}=\begin{Bmatrix}1 & 2-\sqrt{3}\end{Bmatrix}^{\top} \\ \lambda_{2}=1-\sqrt{3},&\phantom{x}\mathbf{v}_{2}=\begin{Bmatrix}1 & 2+\sqrt{3}\end{Bmatrix}^{\top} \end{aligned} $$
Using these results, we have
$$ \begin{Bmatrix} a_{n} \\ b_{n} \end{Bmatrix} = \begin{bmatrix} 1 & 1 \\ 2-\sqrt{3} & 2+\sqrt{3} \end{bmatrix} \begin{bmatrix} \left(1+\sqrt{3}\right)^{n-1} & 0 \\ 0 & \left(1-\sqrt{3}\right)^{n-1} \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 2-\sqrt{3} & 2+\sqrt{3} \end{bmatrix}^{-1} \begin{Bmatrix} a_{1} \\ b_{1} \end{Bmatrix} $$
Substituting $a_{1}=3$ and $b_{1}=1$, we have:
$$ a_{n}=\left(\frac{1}{2}+\frac{1}{3}\sqrt{3}\right)\left(1+\sqrt{3}\right)^{n}+ \left(\frac{1}{2}-\frac{1}{3}\sqrt{3}\right)\left(1-\sqrt{3}\right)^{n} $$