3. In a certain language, there are only two letters A and B. For words of this language, the following rules apply:
1) The only word of length 1 is A.
2) Any sequence of letters $X_{1} X_{2} X_{3} \ldots X_{n} X_{n+1}$, where $X_{i}=\{A, B\}$ for every index $i$, forms a word of length $n+1$ if and only if it contains at least one letter A and is not of the form $X_{1} X_{2} \ldots X_{n} A$, where $X_{1} X_{2} \ldots X_{n}$ is a word of length $n$.

Find a) all words of length 4, b) a formula for the number $p_{n}$ of all words of length $n$.
SOLUTION: a) We will successively find all words of lengths 2, 3, and 4. From the possible groups of length 2, the words are not exactly $B B$ (does not contain any $A$) and $A A$ (is of an impermissible form), so the words are exactly $A B$ and $B A$. From these, we create impermissible forms of length 3: $A B A$ and $B A A$. All other groups of length 3 (except $B B B$) are thus words: $A A A, A A B, A B B, B A B, B B A$. If we append the letter $A$ to their end, we get five impermissible forms of length 4: $A A A A, A A B A, A B B A, B A B A, B B A A$. All other groups of length 4 (except $B B B B$) are thus the sought words: $A A A B, A A B B, A B A A, A B A B, A B B B, B A A A, B A A B$, $B A B B, B B A B, B B B A$.

b) According to part a), we know that $p_{1}=1, p_{2}=2, p_{3}=5$, and $p_{4}=10$. Now, for each $n \geqq 1$, we will express the number $p_{n+1}$ in terms of the number $p_{n}$. To do this, we will divide all words of length $n+1$ into two groups depending on the last letter: those of the form ... A, there are exactly $2^{n}-p_{n}$ (before the last $A$ stands any group of length $n$ that is not a word); those of the form ... B, there are exactly $2^{n}-1$ (before the last $B$ stands any group of length $n$ except $B B \ldots B$). Therefore, $p_{n+1}=\left(2^{n}-p_{n}\right)+\left(2^{n}-1\right)=2^{n+1}-1-p_{n}$. From such expressions for $p_{n+1}$ and $p_{n+2}$, it follows that: $p_{n+2}=2^{n+2}-1-p_{n+1}=2^{n+2}-1-\left(2^{n+1}-1-p_{n}\right)=p_{n}+2^{n+1}$. Based on this, we will determine the values of $p_{n}$ separately for even and odd indices $n$:

$$
\begin{aligned}
p_{2 k-1} & =p_{2 k-3}+2^{2 k-2}=p_{2 k-5}+2^{2 k-4}+2^{2 k-2}=\cdots=p_{1}+2^{2}+2^{4}+\cdots+2^{2 k-4}+2^{2 k-2}= \\
& =1+4+4^{2}+\cdots+4^{k-2}+4^{k-1}=\frac{4^{k}-1}{3}, \\
p_{2 k} & =p_{2 k-2}+2^{2 k-1}=p_{2 k-4}+2^{2 k-3}+2^{2 k-1}=\cdots=p_{2}+2^{3}+2^{5}+\cdots+2^{2 k-3}+2^{2 k-1}= \\
& =2+2 \cdot 4^{1}+2 \cdot 4^{2}+\cdots+2 \cdot 4^{k-2}+2 \cdot 4^{k-1}=\frac{2 \cdot\left(4^{k}-1\right)}{3} .
\end{aligned}
$$

The found formulas hold for any $k \geqq 1$. Let us add that they can be written in a unified form:

$$
p_{n}=\frac{2^{n+2}+(-1)^{n+1}-3}{6} \quad(n=1,2,3,4, \ldots)
$$