A recurrence relation with words, contest type problem 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}}.$$

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$.
