A recurrence relation with words, contest type problem

Question

For a positive integer $n$, a $n$-word is a string of $n$ letters, where each letter is an $A$ or $B$. Let $p_n$ be the number of $n$-words not containing four consecutive $A$ and not containing three consecutive $B$. Find the value of $$\frac{p_{2013}-p_{2011}-p_{2008}}{p_{2010}+p_{2009}}.$$

Answer 1

Let $A_1(n), A_2(n), A_3(n), B_1(n), B_2(n)$ be the number of words with head $(AB, AAB, AAAB, BA, BBA)$, respectively. Then $P(n)=A_1(n)+A_2(n)+A_3(n)+B_1(n)+B_2(n)$, with $$ A_3(n)=A_2(n-1),\quad A_2(n)=A_1(n-1),\quad A_1(n)=B_1(n-1)+B_2(n-1), $$ and $$ B_2(n)=B_1(n-1),\quad B_1(n)=A_1(n-1)+A_2(n-1)+A_3(n-1). $$ Let $A(n)=A_1(n)+A_2(n)+A_3(n), B(n)=B_1(n)+B_2(n)$. So $A_3(n)=B(n-3)$, $A_2(n)=B(n-2)$, $B_2(n)=A(n-2)$, then $$A(n)=B(n-1)+B(n-2)+B(n-3), \quad B(n)=A(n-1)+A(n-2),$$ hence $$ A(n)=A(n-2)+A(n-3)+A(n-3)+A(n-4)+A(n-4)+A(n-5), $$ and $$ B(n)=B(n-2)+B(n-3)+B(n-4)+B(n-3)+B(n-4)+B(n-5) $$ It follows that $$ P(n)=P(n-2)+2P(n-3)+2P(n-4)+P(n-5), $$ obtaining the answer is $2$.