# Finding a Recurrence Relation.

This is from AMC 2015 . For each positive integer n, let S(n) be the number of sequences of length n consisting solely of the letters A and B, with no more than three As in a row and no more than three Bs in a row.

I want to find out a recurrence relation for S(n). I am not able to get it after many tries. I guess its not a simple one.

Any hints are welcome.

• Hint: let $C(n)$ be the number of such sequences that start with $A$, similarly, $D(n)$ is the number of sequences that start with $B$. Observe that $S(n)=C(n)+D(n)$. – Michael Burr Aug 14 '15 at 18:07
• One curiosity question: does the problem say 'find a recurrence for $S(n)$' or does it ask you to find a formula for $S(n)$? – Steven Stadnicki Aug 14 '15 at 18:47
• Hint: Calculate number of not allowed sequences in a sequence of length $n$. – Wojciech Karwacki Aug 14 '15 at 18:51
• @Steven Stadnicki the problem asks for the remainder when S(2015) is divided by 12 – Sudhanshu Aug 14 '15 at 19:22
• @Sudhanshu Ahhh, I see. You can certainly build the recurrence relation, but you may be able to argue by symmetry and get an answer very quickly. – Steven Stadnicki Aug 14 '15 at 21:22

A hint: let $A_1(n)$, $A_2(n)$, and $A_3(n)$ be the number of sequences of length $n$ that end with exactly one, two, and three $A$s respectively, and similarly $B_1(n)$, $B_2(n)$, $B_3(n)$ be the number of sequences of length $n$ that end with exactly one, two, and three $B$s. Then, for instance, $A_2(n+1)=A_1(n)$; a sequence that ends with exactly two $A$s is gotten by appending an $A$ to a sequence that ends with exactly one $A$. You should find most of the recurrence relations trivial; the tricky ones are for $A_1$ and $B_1$. How can you get a sequence with exactly one $A$ at the end of it?
• @Sudhanshu You won't get a direct recurrence relation for $S()$; rather, you'll get (entwined) recurrence relations for $A$ and $B$ - but that's not too complicated, since in fact there's a very obvious relation (what?) between $A_i(n)$ and $B_i(n)$. – Steven Stadnicki Aug 14 '15 at 21:23