Recurrence relation for ways to color a circle with two colors such that there can't be two adjacent reds

Question

Find the recurrence relation for how many ways there are to color a carousel with a circumference of length $n$ with two colors, red and blue such that no two reds will be adjacent

This is like asking about a string of $A,B$ of length $n$ without $AA$ and it can't start and end with $A$.

So: $a_n=\begin{cases} AB\text{____}B = a_{n-3} \\ B\text{______}= a_{n-1} \end {cases}$

$a_n=a_{n-1}+a_{n-3} \\a_1 = 2, a_2 = 3, a_3 =4 $

For $a_3$ these aren't allowed: $\{AAA, AAB, BAA, ABA\}$ so $2^3-4=4$

Can I do this with the beginning and end of the sequence?

Answer 1

I would find it most intuitive to start by having two simultaneous recurrences: $p_n$ is the number of valid strings of length $n$ that start with B and end with A; $q_n$ is the number of valid strings of length $n$ that both start and end with B.

We then have $$ \begin{align} p_n &= q_{n-1} && p_1 = 0 \\ q_n &= p_{n-1} + q_{n-1} && q_1 = 1 \end{align} $$ This gives us $$ \tag{*} q_n = q_{n-1} + q_{n-2} $$ but what we're really interested in is $$ c_n = 2p_n + q_n = 2q_{n-1} + q_n $$ (where the A___B strings count twice because we can use either the string or its reverse). Because this is a linear combination of $q_n$s it will itself satisfy $\text(*)$.