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