2. For any natural number $n$, let us form all possible "words" of length $n$ from the letters $A$ and $B$, and let $p_{n}$ denote the number of those that do not contain any triple $A A A$ of consecutive letters $A$, nor any pair $B B$ of consecutive letters $B$. Determine for which natural numbers $n$ both numbers $p_{n}$ and $p_{n+1}$ are even.
2. Let the number of suitable words of length $n \geq 2$ that end with the pairs of letters $AA, AB, BA$ be denoted by $(aa)_n, (ab)_n, (ba)_n$ respectively; let the number of suitable words of length $n \geq 1$ that end with the letter $A$, respectively $B$, be denoted by $a_n$, respectively $b_n$. For all natural numbers $n \geq 2$, the following holds:

$$
\begin{aligned}
a_{n} & = (aa)_n + (ba)_n, \\
b_{n} & = (ab)_n \\
p_{n} & = a_{n} + b_{n} = (aa)_n + (ba)_n + (ab)_n.
\end{aligned}
$$

There are exactly two suitable words of length one, namely the words $A$ and $B$, and exactly three suitable words of length two, namely the words $AA, AB, BA$, so $a_1 = b_1 = 1, p_1 = 2, (aa)_2 = (ab)_2 = (ba)_2 = 1, a_2 = 2, b_2 = 1, p_2 = 3$.

Every suitable word of length $n \geq 3$ that ends with the pair of letters $AA$ is obtained by appending the letter $A$ to the end of a word of length $n-1$ that ends with the pair $BA$. Therefore, we have

$$
(aa)_n = (ba)_{n-1}
$$

Similarly, we find that for every $n \geq 3$, the following relations also hold:

$$
\begin{aligned}
& (ba)_n = (ab)_{n-1} \\
& (ab)_n = (aa)_{n-1} + (ba)_{n-1}
\end{aligned}
$$

Since we are only interested in the parity of the natural number $p_n$ and the expressions used to calculate it, we can create a table using the symbols $S$ and $L$, which correspond to even and odd numbers, respectively. We get

| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | $\ldots$ |
| ---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $(aa)_n$ |  | $L$ | $L$ | $L$ | $S$ | $S$ | $L$ | $S$ | $L$ | $\cdots$ |
| $(ba)_n$ |  | $L$ | $L$ | $S$ | $S$ | $L$ | $S$ | $L$ | $L$ | $\cdots$ |
| $(ab)_n$ |  | $L$ | $S$ | $S$ | $L$ | $S$ | $L$ | $L$ | $L$ | $\ldots$ |
| $a_n$ | $L$ | $S$ | $S$ | $L$ | $S$ | $L$ | $L$ | $L$ | $S$ | $\cdots$ |
| $b_n$ | $L$ | $L$ | $S$ | $S$ | $L$ | $S$ | $L$ | $L$ | $L$ | $\cdots$ |
| $p_n$ | $S$ | $L$ | $S$ | $L$ | $L$ | $L$ | $S$ | $S$ | $L$ | $\ldots$ |

This table is necessarily periodic because there are only eight different ordered triples of the letters $S$ and $L$, so the values of the sequences $\left((aa)_n\right), \left((ba)_n\right), \left((ab)_n\right)$ will start repeating after at most eight columns. The values of the sequences $\left(a_n\right), \left(b_n\right), \left(p_n\right)$ are derived from them, so they will also start repeating. From the table, we see that its period is 7 (the first two identical columns are for $n=2$ and $n=9$). Since in the relevant segment of the table the pair of consecutive even numbers $p_7, p_8$ is unique, both numbers $p_n$ and $p_{n+1}$ are even if and only if the number $n$ is divisible by seven.

Note 1. From the above relations, we can derive recurrence equations for the numbers $a_n$ and $b_n$. For all natural numbers $n \geq 4$, the following holds:

$$
\begin{aligned}
& a_n = (aa)_n + (ba)_n = (ba)_{n-1} + (ab)_{n-1} = (ab)_{n-2} + (ab)_{n-1} = b_{n-2} + b_{n-1}, \\
& b_n = (ab)_n = (aa)_{n-1} + (ba)_{n-1} = a_{n-1}.
\end{aligned}
$$

These equations can also be derived by the following reasoning. A suitable word ending with the letter $A$ has the suffix $BA$ or $BAA$, the number of words of the first type is $b_{n-1}$, and the number of words of the second type is $b_{n-2}$. A suitable word ending with the letter $B$ necessarily has the suffix $AB$, and there are $a_{n-1}$ such words.

Note 2. From the relations mentioned in Note 1, a recurrence equation can be derived directly for the numbers $p_n$. For every $n \geq 4$, we have:

$$
\begin{aligned}
a_n & = b_{n-1} + b_{n-2} = a_{n-2} + a_{n-3}, \\
b_n & = a_{n-1} = b_{n-2} + b_{n-3}
\end{aligned}
$$

Given that $p_n = a_n + b_n$, we get by adding these relations the equation

$$
p_n = p_{n-2} + p_{n-3},
$$

which can also be derived as follows: Every suitable word of length $n$ has exactly one of the suffixes $ABA, ABA, BAB, BAA$, and the suffixes $ABA$ and $BAB$ are found in exactly $p_{n-2}$ words, while the suffixes $BAA$ and $BAA$ are found in exactly $p_{n-3}$ words.

A full solution is worth 6 points. For any complete system of equations that allows the recursive calculation of the numbers $p_n$, award 4 points.