1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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)$. $\endgroup$ – Michael Burr Aug 14 '15 at 18:07
  • $\begingroup$ 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)$? $\endgroup$ – Steven Stadnicki Aug 14 '15 at 18:47
  • $\begingroup$ Hint: Calculate number of not allowed sequences in a sequence of length $n$. $\endgroup$ – Wojciech Karwacki Aug 14 '15 at 18:51
  • $\begingroup$ @Steven Stadnicki the problem asks for the remainder when S(2015) is divided by 12 $\endgroup$ – Sudhanshu Aug 14 '15 at 19:22
  • $\begingroup$ @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. $\endgroup$ – Steven Stadnicki Aug 14 '15 at 21:22
2
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ I tried writing A1(n) in terms of other smaller A1's but the resultant series was too large. How to simplify? $\endgroup$ – Sudhanshu Aug 14 '15 at 18:41
  • $\begingroup$ @Sudhanshu What do you mean by 'too large'? $\endgroup$ – Steven Stadnicki Aug 14 '15 at 18:46
  • $\begingroup$ I meant that it had a lot of a1's and I was not getting a method to simplify it in terms of S(n-1) and such.. $\endgroup$ – Sudhanshu Aug 14 '15 at 19:21
  • $\begingroup$ @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)$. $\endgroup$ – Steven Stadnicki Aug 14 '15 at 21:23
  • $\begingroup$ Isn't A1(n+1)= B1(n) + B2(n) +B3(n) = B1(n) +B1(n-1) +B1(n-2) $\endgroup$ – Sudhanshu Aug 15 '15 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.