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

-
Can you tell us the source of the problem? – EuYu May 5 '13 at 8:42
For displayed equations, the punctuation needs to be included within the double dollar signs (ideally offset by a \; space); otherwise it ends up on the following line, as you can see here. (Note that there's a preview in the edit area where you can check the formatting of your question before posting it.) – joriki May 5 '13 at 8:43
@EnYu : It is one of my homework problem of a course about problem solving. – Ishigami May 5 '13 at 14:11

## 1 Answer

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

-
Nice. But the answer is $2$, not $1/2$. – joriki May 5 '13 at 19:31
@joriki final step mistake... – Ma Ming May 5 '13 at 19:44