Example 18 Let $a_{n}$ be the number of $n$-digit numbers, formed by $1,2,3,4,5$, that have at least 3 different digits, where 1 and 2 are not adjacent. Find $a_{n}$ and $a_{5}$.
Let $x_{n}$ be the number of $n$-digit numbers formed by $1,2,3,4,5$ where 1 and 2 are not adjacent, $b_{n}$ be the number of such $n$-digit numbers ending in 1 or 2, $c_{n}$ be the number of such $n$-digit numbers not ending in 1 or 2, and $y_{n}$ be the number of $n$-digit numbers with at most two different digits. Then,
$$
a_{n}=x_{n}-y_{n}, x_{n}=b_{n}+c_{n} .
$$

The $b_{n}$ $n$-digit numbers ending in 1 or 2 and where 1 and 2 are not adjacent can be divided into two categories: those ending in 1 or 2 with the second last digit not being 1 or 2, which are $2 c_{n-1}$ in number, and those ending in 11 or 22, which are $b_{n-1}$ in number. Thus,
$$
b_{n}=b_{n-1}+2 c_{n-1} \text {. }
$$

The $c_{n}$ $n$-digit numbers ending in 3, 4, or 5 and where 1 and 2 are not adjacent have the first $n-1$ digits forming an $n-1$-digit number where 1 and 2 are not adjacent, so
$$
c_{n}=3 x_{n-1} \text {. }
$$

By eliminating $b_{n}$ and $c_{n}$ from (1), (2), and (3), we get $x_{n}-4 x_{n-1}-3 x_{n-2}=0$.
The characteristic equation is $r^{2}-4 r-3=0$, with roots $r_{1,2}=2 \pm \sqrt{7}$, hence
$$
x_{n}=k_{1}(2+\sqrt{7})^{n}+k_{2}(2-\sqrt{7})^{n} \text {. }
$$

Define $x_{0}$ such that $x_{2}-4 x_{1}-3 x_{0}=0$. Given $x_{1}=5, x_{2}=2^{5}-2=23$, we get $x_{0}=1$, thus
$$
\left\{\begin{array}{l}
k_{1}+k_{2}=1, \\
k_{1}(2+\sqrt{7})+k_{2}(2-\sqrt{7})=5,
\end{array}\right.
$$

Solving, we get $k_{1}=\frac{3+\sqrt{7}}{2 \sqrt{7}}, k_{2}=-\frac{3-\sqrt{7}}{2 \sqrt{7}}$, so
$$
x_{n}=\frac{3+\sqrt{7}}{2 \sqrt{7}}(2+\sqrt{7})^{n}-\frac{3-\sqrt{7}}{2 \sqrt{7}}(2-\sqrt{7})^{n}.
$$

There are $C_{5}^{1}=5$ $n$-digit numbers with all digits the same, and $n$-digit numbers with exactly two different digits and 1 and 2 adjacent are $\left(C_{5}^{2}-1\right)\left(2^{n}-2\right)=9 \cdot 2^{n}-18$ in number, so $y_{n}=5+9 \cdot 2^{n}-18=9 \cdot 2^{n}-13$, thus
$$
a_{n}=x_{n}-y_{n}=\frac{3+\sqrt{7}}{2 \sqrt{7}}(2+\sqrt{7})^{n}-\frac{3-\sqrt{7}}{2 \sqrt{7}}(2-\sqrt{7})^{n}-9 \cdot 2^{n}-13 .
$$

Given $x_{1}=5, x_{2}=23, x_{3}=4 x_{2}+3 x_{1}=107, x_{4}=4 x_{3}+3 x_{2}=497, x_{5}=4 x_{4}+3 x_{3}=$ $2309, y_{5}=9 \cdot 2^{5}-13=275$, we have $a_{5}=x_{5}-y_{5}=2309-275=2034$.