4. How many positive integers satisfy that in their decimal representation they have exactly 150 digits, and any two adjacent digits differ by $\pm 2$? (2013-2014 Hungarian Mathematical Olympiad)
Let $a_{i, j}$ denote the number of $i$-digit numbers whose first digit is $j$ (which can be 0) and where the difference between any two adjacent digits is $\pm 2$.

Use mathematical induction to prove: For any positive integer $k$, we have
$$
\begin{array}{l}
a_{2 k, 0}=a_{2 k, 1}=a_{2 k, 8}=a_{2 k, 9}=3^{k-1}, \\
a_{2 k, j}=2 \times 3^{k-1}(2 \leqslant j \leqslant 7) .
\end{array}
$$

Thus, the number of such positive integers is
$$
\begin{array}{l}
a_{150,1}+a_{150,2}+\cdots+a_{150,9} \\
=(3 \times 1+6 \times 2) \times 3^{74}=5 \times 3^{75} .
\end{array}
$$