Find a recursive definition of this sequence

We can write down an infinite recursion and then simplify.

Let $A_n$ be the number of such sequences ending in A, and $B_n$ be the number of such sequences ending in B. We count the empty string in both.

Then, for $n \ge 1$, we have $$ A_n = B_{n-1} + B_{n-3} + B_{n-4} + B_{n-5} + \dotsb $$ because we can add A or AAA or AAAA or AAAAA to the end of a string ending in B, but not both. So for $n \ge 2$, we have \begin{align} A_n - A_{n-1} &= (B_{n-1} + B_{n-3} + B_{n-4} + B_{n-5} + \dotsb) - (B_{n-2} + B_{n-4} + B_{n-5} + B_{n-6} + \dotsb) \\ &= B_{n-1} - B_{n-2} + B_{n-3}. \\ A_n &= A_{n-1} + B_{n-1} - B_{n-2} + B_{n-3}. \end{align} We can do the same thing for $B_n$, except that $B_n$ won't have an $A_{n-3}$ term in the recurrence. For $n\ge 2$, we get \begin{align} B_n - B_{n-1} &= (A_{n-1} + A_{n-4} + A_{n-5} + \dotsb) - (A_{n-2} + A_{n-5} + A_{n-6} + \dotsb) \\ &= A_{n-1} - A_{n-2} + A_{n-4}. \\ B_n &= A_{n-1} + B_{n-1} - A_{n-2} + B_{n-4}. \end{align} This is already enough to make the problem a finite linear recurrence, but we can still try to simplify it further.

---

For $n \ge 1$, we have $W_n = A_n + B_n$, so we have $$ W_n = 2W_{n-1} - W_{n-2} +B_{n-3} + A_{n-4} $$ by adding the two equations. Unfortunately, we still have a mismatched $A$ and $B$ to deal with here.

Expanding $B_{n-3}$ and $A_{n-4}$ out using their recurrences, we get \begin{align} W_{n} &= 2W_{n-1} - W_{n-2} + (W_{n-4} - A_{n-5} + A_{n-7}) + (W_{n-5} - B_{n-6} + B_{n-7}) \\ &= 2W_{n-1} - W_{n-2} + W_{n-4} + W_{n-5} - A_{n-5} - B_{n-6} + W_{n-7} \end{align} which again has a mismatched $A$ and $B$, but now in the reverse order. So if we subtract $W_{n-2}$ from both sides, we get \begin{align} W_n - W_{n-2} &= (2W_{n-1} - W_{n-2} + W_{n-4} + W_{n-5} - A_{n-5} - B_{n-6} + W_{n-7}) \\&\quad - (2W_{n-3} - W_{n-4} + B_{n-5} + A_{n-6}) \\ &= 2W_{n-1} - W_{n-2} - 2W_{n-3} + 2W_{n-4} - W_{n-6} + W_{n-7} \end{align}

and the final recursion is $W_n = 2W_{n-1} - 2W_{n-3} + 2 W_{n-4} - W_{n-6} + W_{n-7}$. (This may not fly for small $n$ - in particular, $W_0 \ne A_0 + B_0$ - but for $n> 7$ all the manipulations above are valid.)

Maybe this graph will be of assistance:

You want to count the walks of length $n$ starting from the left-most state and ending up in any of the blue states.

Let $w(n)$ be the number of qualifying words of length $n$.

Then $w$ satisfies the recursion $$w(n)=2w(n-1)-2w(n-3)+2w(n-4)-w(n-6)+w(n-7)$$ for $n\ge 8$, with initial values \begin{align*} w(0)&=1\\ w(1)&=2\\ w(2)&=2\\ w(3)&=3\\ w(4)&=6\\ w(5)&=11\\ w(6)&=18\\ w(7)&=30\\ \end{align*} The above recursion can be derived as follows . . .

Define functions $a_1,a_3,b_1,b_4$ by

• $a_1(n)$ is the number of qualifying words of length n for which the last constant block is exactly "A".
• $a_3(n)$ is the number of qualifying words of length n for which the last constant block ends with "AAA" (i.e., at least $3$ consecutive occurrences of "A").$\\[6pt]$
• $b_1(n)$ is the number of qualifying words of length n for which the last constant block is exactly "B".
• $b_4(n)$ is the number of qualifying words of length n for which the last constant block ends with "BBBB" (i.e., at least $4$ consecutive occurrences of "B").

Then we get the following linked recursion: \begin{align*} w(n)&= \begin{cases} 1\;\text{if}\;n=0\\ a_1(n)+a_3(n)+b_1(n)+b_4(n)\;\text{if}\;n > 0\tag{eq1}\\ \end{cases} \\[4pt] a_1(n)&= \begin{cases} 0\;\text{if}\;n<1\\ 1\;\text{if}\;n=1\\ b_1(n-1)+b_4(n-1)\;\text{if}\;n > 1\tag{eq2}\\ \end{cases} \\[4pt] a_3(n)&= \begin{cases} 0\;\text{if}\;n<3\\ 1\;\text{if}\;n=3\\ b_1(n - 3) + b_4(n - 3)+a_3(n-1)\;\text{if}\;n > 3\tag{eq3}\\ \end{cases} \\[4pt] b_1(n)&= \begin{cases} 0\;\text{if}\;n<1\\ 1\;\text{if}\;n=1\\ a_1(n-1)+a_3(n-1)\;\text{if}\;n > 1\tag{eq4}\\ \end{cases} \\[4pt] b_4(n)&= \begin{cases} 0\;\text{if}\;n<4\\ 1\;\text{if}\;n=4\\ a_1(n - 4) + a_3(n - 4)+b_4(n-1)\;\text{if}\;n > 4\tag{eq5}\\ \end{cases} \\[4pt] \end{align*} Applying the linked recursion, we get \begin{align*} w(0)&=1\\ w(1)&=2\\ w(2)&=2\\ w(3)&=3\\ w(4)&=6\\ w(5)&=11\\ w(6)&=18\\ w(7)&=30\\ \end{align*} Next, we unlink the linked recursion . . .

Using $(\text{eq}2)$, we can eliminate $a_1$.

Then, using $(\text{eq}4)$, we can eliminate $b_1$.

Then, using $(\text{eq}5)$, we can eliminate $a_3$.

Based on the eliminations, from $(\text{eq}1)$ we get $$ w(n)=2b_4(n+3)-4b_4(n+1)+3b_4(n)+2b_4(n-1)-3b_4(n-2)+b(n-3)+b(n-4)-b_4(n-5) $$ for $n\ge 6$, and from $(\text{eq}3)$ we get $$ b_4(n)=2b_4(n-1)-2b_4(n-3)+2b_4(n-4)-b_4(n-6)+b_4(n-7) $$ for $n\ge 8$.

Since shifts of $b$ satisfy the same recursion as $b$, and since $w$ is a linear combination of $b$ and shifts of $b$, it follows that $w$ also satisfies the same recursion as $b$, hence we get $$w(n)=2w(n-1)-2w(n-3)+2w(n-4)-w(n-6)+w(n-7)\tag{eq6}$$ for $n\ge 13$.

We already have the values of $w(n)$ for $0\le n\le 7$.

Applying the linked recursion, we can get the values of $w(n)$ for $8\le n\le 12$, and it can then be verified that $(\text{eq}6)$ fails for $n=7$, but holds for $8\le n\le 12$, hence holds for all $n\ge 8$.