Three. (50 points) Let $n$ be a positive integer. In the decimal digits of an $n$-digit number, if it contains the digit 8, then the digit immediately before each 8 cannot be the digit 3 (i.e., the substring "38" cannot appear). Find the number of all such $n$-digit numbers.

Translate the above text into English, preserving the original text's line breaks and format, and output the translation result directly.
Three, consider the number of $n+1(n \geqslant 1)$-digit numbers $a_{n+1}$, and divide into the following two cases.
(1) When the unit digit is not 8, the first $n$ digits have $a_{n}$ ways of selection, and the unit digit has 9 ways of selection, thus, the $n+1$-digit number has $9 a_{n}$ ways of selection.
(2) When the unit digit is 8, it can be divided into the following three categories:
From this, we know that the number of $n+1$-digit allowed positive integers with the unit digit being 8 is
$$
1+7+\sum_{k=1}^{n-1} 8 a_{n-k}=8+8 \sum_{k=1}^{n-1} a_{n-k} .
$$

From (1) and (2), we get
$$
\begin{array}{l}
a_{n+1}=9 a_{n}+8+8\left(a_{1}+a_{2}+\cdots+a_{n-1}\right) \\
=8+a_{n}+8\left(a_{1}+a_{2}+\cdots+a_{n}\right) .
\end{array}
$$

From (1), we get
$$
a_{n+2}=8+a_{n+1}+8\left(a_{1}+a_{2}+\cdots+a_{n+1}\right) \text {. }
$$

From (2) - (1), we get
$$
a_{n+2}-a_{n+1}=a_{n+1}-a_{n}+8 a_{n+1},
$$

which is $a_{n+2}=10 a_{n+1}-a_{n}(n=1,2, \cdots)$.
It is easy to know that $a_{1}=9, a_{2}=9 a_{1}+8=81+8=89$.
From equation (3), we know $a_{n}=A(5+2 \sqrt{6})^{n-1}+B(5-2 \sqrt{6})^{n-1}$, where $A, B$ are undetermined constants, then
$$
\left\{\begin{array}{l}
A+B=9, \\
(5+2 \sqrt{6}) A+(5-2 \sqrt{6}) B=89 .
\end{array}\right.
$$

Solving, we get $A=\frac{22+9 \sqrt{6}}{2 \sqrt{6}}, B=\frac{-22+9 \sqrt{6}}{2 \sqrt{6}}$.
Thus, $a_{n}=\frac{22+9 \sqrt{6}}{2 \sqrt{6}}(5+2 \sqrt{6})^{n-1}+\frac{-22+9 \sqrt{6}}{2 \sqrt{6}}(5-2 \sqrt{6})^{n-1}$.
This is the number of $n$-digit positive integers that meet the requirements.
(Wu Weizhao, School of Mathematics and Information Science, Guangzhou University,
510006)