Bogdanov I.i.

Petya wants to list all possible sequences of 100 natural numbers, in each of which the number 4 or 5 appears at least once, and any two adjacent members differ by no more than 2. How many sequences will he have to list?
Let's find the answer for similar sequences of $n$ natural numbers.

First method. We call a sequence of $n$ natural numbers, any two adjacent members of which differ by no more than 2, interesting. To each interesting sequence $a_{1}, a_{2}, \ldots, a_{n}$, we associate a difference sequence $b_{i}=a_{i+1}-a_{i}(i=1,2, \ldots, n-1)$. All members of the difference sequence are equal to $0, \pm 1$ or $\pm 2$, so the number of all possible difference sequences is $5^{n-1}$. First, let's count the number $S$ of all interesting sequences, the minimum member of which does not exceed 5. Consider an arbitrary difference sequence $b_{1}, b_{2}, \ldots, b_{n-1}$. Any two interesting sequences corresponding to it differ by adding the same number to each member. Therefore, among them, there is exactly one sequence with the minimum member equal to $1,2,3,4$ or 5. Thus, $S=5 \cdot 5^{n-1}=5^{n}$.

In $S$, all sequences written by Petya are counted, and a few extra ones - those in which neither 4 nor 5 appears. It is clear that if an interesting sequence contains both numbers greater than 5 and less than 4, then 4 or 5 will also appear. But the minimum member of each extra sequence is no more than 3, meaning that all its members do not exceed 3. Therefore, all extra sequences consist of the numbers 1, 2, and 3. On the other hand, every sequence of the numbers 1, 2, and 3 is interesting, and thus extra.

Therefore, the number of extra sequences is exactly $3^{n}$, and the desired number is $S-3^{n}=5^{n}-3^{n}$.

Second method. We call an interesting sequence good if it contains the number 4 or 5 at least once. Let $S_{n}$ be the number of good sequences of length $n$. We will prove by induction on $n$ that $S_{n} = 5^{n} - 3^{n}$. The base case $(n=1)$ is obvious.

Inductive step. Consider an arbitrary $n$-member good sequence; let it end with the number $k$. Then we can append any number from $k-2$ to $k+2$ to it; the resulting sequence will be good if the appended number is natural. If the appended number is non-positive (i.e., 0 or -1), then after appending, we add 5 to all numbers in the sequence. The resulting sequence will end with the number 4 or 5, and thus will be good.

Note that all the resulting sequences are different. For sequences obtained without adding 5, this is obvious; and in this way, we obtain exactly all good sequences among the first $n$ members of which there is a 4 or 5. The sequences obtained by adding 5 are also pairwise different; and these are exactly all good sequences whose first $n$ members are greater than 5, and among which there is a 9 or 10. In particular, these sequences are different from those described earlier. Thus, we have so far constructed $5 S_{n}$ good $(n+1)$-member sequences.

It remains to count the number of uncounted sequences. In each uncounted sequence, among the first $n$ members, there are no numbers 4, 5, 9, and 10, and the last member is 4 or 5. Therefore, either the first $n$ members are ones, twos, and threes, or they are all sixes, sevens, or eights. Let's count the number of the first; the number of the second is counted similarly.

Consider any sequence of $n$ ones, twos, and threes (its adjacent members automatically differ by at most 2). If it ends with the number 3, then we can append 4 or 5, obtaining an uncounted sequence. If it ends with the number 2, then we can append only 4; if its last number is 1, then we cannot obtain a good sequence from it. Therefore, the number of obtained uncounted sequences is $2 \cdot 3^{n-1} + 3^{n-1} = 3^{n}$ (and the same number is obtained from sequences with numbers 6, 7, and 8).

Thus, $S_{n+1} = 5 S_{n} + 2 \cdot 3^{n} = 5(5^{n} - 3^{n}) + 2 \cdot 3^{n} = 5^{n+1} - 3^{n+1}$

## Answer

$5^{100} - 3^{100}$