Example 2-50 Find the number of n-bit binary numbers in which the pattern 010 appears for the first time in the last 3 bits.
To find the number of $n$-bit binary numbers $b_{1} b_{2} \cdots b_{n}$ that, when scanned from left to right, have the pattern 010 appear for the first time in the last 3 bits. Naturally, excluding the last 3 bits, no other 3 consecutive bits should form the pattern 010.

Let $a_{n}$ denote the number of $n$-bit numbers that satisfy this condition. Similar to the previous example, there are $2^{n-3}$ $n$-bit binary numbers whose last 3 bits are 010. Analyzing these $2^{n-3}$ numbers as follows:
(1) It includes the numbers where the pattern 010 appears for the first time in the last 3 bits, the number of such numbers is $a_{n}$, excluding the possibility of the pattern 010 appearing for the first time in the $(n-4)$ to $(n-2)$ positions.
(2) It includes the numbers where the pattern 010 appears for the first time in the $(n-4)$ to $(n-2)$ positions, the number of such numbers is $a_{n}$. This can be visually represented as:
(3) It includes the numbers where the pattern 010 appears for the first time in the $(n-5)$ to $(n-3)$ positions, the number of such numbers is $a_{n-3}$. This can be visually represented as:
(4) It includes the numbers where the pattern 010 appears for the first time in the $(n-6)$ to $(n-4)$ positions, the number of such numbers is $2 a_{n+1}$, because the $(n-3)$-th bit (marked with *) can take 0 or 1, two states. This can be visually represented as:

In general, for $k \geqslant 3$, the number of $n$-bit numbers where the pattern 010 appears for the first time in the $(n-k-2)$ to $(n-k)$ positions is $2^{k-3} a_{n}$. The $(k-3)$ bits between the $(n-k)$-th and $(n-3)$-th positions can take 0 or 1, hence there are $2^{k-3}$ states. This can be visually represented as:

Thus, the recurrence relation is:
$$
\begin{array}{c}
a_{n}+a_{n-2}+a_{n-3}+2 a_{n-4}+\cdots+2^{n-6} a_{3}=2^{n-3}, n \geqslant 6 \\
a_{3}=1, \quad a_{4}=2, \quad a_{5}=3
\end{array}
$$

When $n=5$, the following states exist:
$$
00010,10010,11010
$$

Excluding 01010, because 01010 has the pattern 010 appearing in the first 3 bits when scanned from left to right.
Note that the derived recurrence relation is quite special, with a variable order. The characteristic value method discussed earlier does not apply to it.
$$
a_{3}=1, \quad a_{4}=2, \quad a_{5}=3
$$

When $n=6$, we have

Thus,
$$
\begin{array}{l}
a_{6}+a_{4}+a_{3}=2^{3} \\
a_{6}=8-a_{4}-a_{3}=5
\end{array}
$$

When $n=7$, we have
$$
\begin{array}{l}
a_{7}+a_{5}+a_{4}+2 a_{3}=2^{4} \\
a_{7}=16-a_{5}-a_{4}-2 a_{3}=9
\end{array}
$$

And so on.
Let $A(x)=1+2 x+3 x^{2}+a_{6} x^{3}+a_{7} x^{4}+\cdots$
$$
\begin{array}{l}
x^{3}: a_{6}+a_{4}+a_{3}=2^{3} \\
x^{4}: a_{7}+a_{5}+a_{4}+2 a_{3}=2^{4} \\
x^{5}: a_{8}+a_{6}+a_{5}+2 a_{4}+2^{2} a_{3}=2^{5} \\
+ \text { ) } \quad \text {. } \\
{\left[A(x)-1-2 x-3 x^{2}\right]+x^{2}[A(x)-1]} \\
+\left(x^{3}+2 x^{4}+2^{2} x^{5}+\cdots\right) A(x) \\
=\frac{2^{3} x^{3}}{1-2 x} \\
\end{array}
$$

After rearranging, we get
$$
\begin{array}{c}
\left(1+x^{2}+\frac{x^{3}}{1-2 x}\right) A(x)=\frac{2^{3} x^{3}}{1-2 x}+1+2 x+4 x^{2} \\
\frac{1-2 x+x^{2}-2 x^{3}+x^{3}}{1-2 x} A(x)=\frac{2^{3} x^{3}+1-4 x^{2}+4 x^{2}-8 x^{3}}{1-2 x}=\frac{1}{1-2 x}
\end{array}
$$

Thus,
$$
A(x)=\frac{1}{1-2 x+x^{2}-x^{3}}=1+2 x+3 x^{2}+5 x^{3}+9 x^{4}+16 x^{5}+28 x^{6}+49 x^{7}+\cdots
$$

That is, $a_{3}=1, a_{4}=2, a_{5}=3, a_{6}=5, a_{7}=9, a_{8}=16, a_{9}=28, a_{10}=49, \cdots$