Example 2-49 Find the number of images of $n$-bit binary numbers where the last 3 bits are 010.
To find the recurrence relation for the sequence $a_{n}$, it is necessary to analyze the structure of the numbers that satisfy the condition. Since in $n$ bits, except for the last 3 bits which are 010, the remaining $n-3$ bits can be 0 or 1, as shown in (a):
$n$ bits
(a):

Therefore, the number of $n$-bit binary numbers with the last 3 bits being 010 is $2^{n-3}$. This includes two types of numbers: those where the last 3 bits form the 010 pattern and those where the 010 pattern appears from the $(n-4)$-th to the $(n-2)$-th bit, but not in the last 3 bits, as follows:
$$
\underbrace{\times \times \cdots \times}_{1 \sim n-5 \text { bits }} \underbrace{0 \quad 1 \quad 0}_{n-4 \sim n-2 \text { bits }} 10
$$

Thus, we have
$$
\begin{array}{c}
a_{n}+a_{n-2}=2^{n-3}, n \geqslant 5 \\
a_{3}=1, \quad a_{4}=2
\end{array}
$$

Using equation (2-8), we get $a_{2}=0, a_{1}=0, a_{0}=\frac{1}{2}$.
The characteristic equation is
$$
\begin{array}{l}
(x-2)\left(x^{2}+1\right)=0 \\
x_{1}=2, x_{2,3}=\mathrm{e}^{ \pm \frac{\pi}{2}}
\end{array}
$$

Let
$$
a_{n}=A \cos \left(n \cdot \frac{\pi}{2}\right)+B \sin \left(n \cdot \frac{\pi}{2}\right)+C \cdot 2^{n}
$$

Solving the system of equations
$$
\left\{\begin{array}{l}
A+C=\frac{1}{2} \\
B+2 C=0 \\
-A+4 C=0
\end{array}\right.
$$

We get
$$
\left\{\begin{array}{l}
A=\frac{2}{5} \\
B=-\frac{1}{5} \\
C=\frac{1}{10}
\end{array}\right.
$$

Therefore,
$$
a_{n}=\frac{2}{5} \cos \left(n \cdot \frac{\pi}{2}\right)-\frac{1}{5} \sin \left(n \cdot \frac{\pi}{2}\right)+\frac{1}{10} \cdot 2^{n}, n \geqslant 3
$$