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 words that do not contain the quadruple $AAAA$ of consecutive letters $A$, nor the triple $BBB$ of consecutive letters $B$. Determine the value of the expression

$$
\frac{p_{2004}-p_{2002}-p_{1999}}{p_{2001}+p_{2000}}
$$

(R. Kučera)
Solution. Let the number of suitable words of length $n$ ending with the letter $A$, respectively $B$, be denoted by $a_{n}$, respectively $b_{n}$. Then

$$
p_{n}=a_{n}+b_{n} \text {. }
$$

Let $n \geqq 4$. A suitable word ending with the letter $A$ has one of the endings $B A, B A A$, or $B A A A$. The number of words of the first type is $b_{n-1}$, of the second type $b_{n-2}$, and of the third type $b_{n-3}$. Therefore,

$$
a_{n}=b_{n-1}+b_{n-2}+b_{n-3} .
$$

Similarly, for $n \geqq 3$, a suitable word ending with the letter $B$ has one of the endings $A B$, $A B B$, thus

$$
b_{n}=a_{n-1}+a_{n-2} .
$$

Now let $n \geqq 6$; each of the numbers $b_{i}$ in relation (2) can be expressed using (3), giving us

$$
\begin{aligned}
a_{n} & =b_{n-1}+b_{n-2}+b_{n-3}= \\
& =\left(a_{n-2}+a_{n-3}\right)+\left(a_{n-3}+a_{n-4}\right)+\left(a_{n-4}+a_{n-5}\right)= \\
& =a_{n-2}+2 a_{n-3}+2 a_{n-4}+a_{n-5} .
\end{aligned}
$$

Similarly, we get

$$
\begin{aligned}
b_{n} & =a_{n-1}+a_{n-2}= \\
& =\left(b_{n-2}+b_{n-3}+b_{n-4}\right)+\left(b_{n-3}+b_{n-4}+b_{n-5}\right)= \\
& =b_{n-2}+2 b_{n-3}+2 b_{n-4}+b_{n-5} .
\end{aligned}
$$

By adding equations (4) and (5), we get from (1)

$$
p_{n}=p_{n-2}+2 p_{n-3}+2 p_{n-4}+p_{n-5} \text {. }
$$

Therefore, for any natural number $n \geqq 6$,

$$
\frac{p_{n}-p_{n-2}-p_{n-5}}{p_{n-3}+p_{n-4}}=2,
$$

thus the given fraction has the value 2 even for $n=2004$.