Finding a recursive formula for a string of the letters $A,B,C$ such that $AB, BC$ does not appear in

Question

Find a recursive formula for a string of the letters $A,B,C$ such that $AB, BC$ does not appear in.

$a_n=\begin {cases}A\text{____}a_{n-1}\\ B\text{____}a_{n-1}\\ C\text{____}a_{n-1}\\ -BC\text{____}a_{n-2}\\ -AB\text{____}a_{n-2}\\ -ABC\text{____}a_{n-3} \end{cases}$

So the sequence is $a_n=3a_{n-1}-2a_{n-2}-a_{n-3}$ and the starting conditions are trivial.

But I'm not sure about the $ABC$ part isn't it a double count since I already have the $AB, BC$?

Answer 1

Update: see below for a simpler derivation

Let $x_n$ be $n-$length allowed sequences, $a_n$ be the sequences ending on $A$, $b_n$ the sequences ending on $B$...

Then $$a_{n+1}=a_n+b_n +c_n \tag{1}$$ $$b_{n+1}=b_n +c_n\tag{2}$$ $$c_{n+1}=a_n +c_n\tag{3}$$

Replacing $(2)$ into $(1)$ we get rid of $b_n$:

$$ a_{n+2}-2a_{n+1} +a_n -c_{n+1}=0 \tag{4}$$

Together with $(3)$ this gives $$c_n = a_{n+2}-2a_{n+1} \tag{5}$$

Replacing this again in $(4)$ we get rid of $c_n$:

$$a_{n+3}=3a_{n+2}-2 a_{n+1}+a_n$$

Now, because $x_n=a_n+b_n+c_n=a_{n+1}$ this implies

$$ x_{n+1}=3 x_{n}-2x_{n-1}+x_{n-2}$$

Starting with $x_0=1$, $x_1=3$, $x_2=7$, this gives the sequence $1,3,7,16,37,86, 200 \cdots$

---

Update: a simpler derivation:

Let $x_n$ be the valid sequences of length $n$. Then $x_{n} = 3 x_{n-1} - y_{n}$ where $y_{n}$ are invalid sequences of length $n$, which are valid up to $n-1$. These correspond to such sequences ending on $AB$ (this count is $x_{n-2}$) plus such sequences ending on $BC$ (this count is $x_{n-2}-x_{n-3}$ - the last term accounts for the ending $ABC$ subsequence)

Then, $$x_n = 3 x_{n-1} - (x_{n-2} +x_{n-2} -x_{n-3})=3 x_{n-1} - 2 x_{n-2} +x_{n-3}$$

Answer 2

I think the last term in your recurrence should be PLUS a(n-3). I solve these problems using systems of generating functions. This sequence is Sloane's OEIS A095263. If it helps you to see my Mathematica code then look below. The functions a[x], b[x], and c[x] are respectively the g.f.'s for valid words starting with A, starting with B, and empty or starting with C. What we want is a[x]+b[x]+c[x]. The method is a bit subtle but it seems very fruitful in terms of economy of thought.

sol = Solve[{a[x] == x a[x] + x c[x], b[x] == x a[x] + x b[x] + x, c[x] == 1 + x a[x] + x b[x] + x c[x]}, {a[x], b[x], c[x]}]

{{a[x] -> -((x - x^2 + x^3)/(-1 + 3 x - 2 x^2 + x^3)), b[x] -> ((-1 + x) x)/(-1 + 3 x - 2 x^2 + x^3), c[x] -> ((-1 + x) (1 - x + x^2))/(-1 + 3 x - 2 x^2 + x^3)}}

Simplify[a[x] + b[x] + c[x] /. sol]

1/(1 - 3 x + 2 x^2 - x^3)

nn = 10; CoefficientList[Series[1/(1 - 3 x + 2 x^2 - x^3), {x, 0, nn}], x]

{1, 3, 7, 16, 37, 86, 200, 465, 1081, 2513, 5842}