Finding recurrence relation for strings of length n formed from A, B, C?

Question

Let $S_n$ be the number of strings of length $n$ formed from letters A, B, C, that do not contain substrings AB, BA, AAA or BBB. For example, for $n = 3$, all strings with this property are:

AAC, ACA, ACB, ACC, BBC, BCA, BCB, BCC, CAA, CAC, CBB, CBC, CCA, CCB, CCC,

and thus $S_3 = 15$. (Note that $S_0 = 1$, because the empty string satisfies the condition.) Derive a recurrence relation for the numbers $S_n$. You need to provide a complete justification for this recurrence. (But you do not need to solve it.)

I came up with $S_n = 2S_{n - 1} + 1$ but I am fairly certain that is wrong and anyways I cannot prove it logically. Can someone point me in the right direction? $S_0$ and $S_3$ are given and I believe $S_1 = 3$ and $S_2 = 7$. Thanks in advance!

Answer 1

Hint: Consider three types of string: those that end in $C$, those that end in a single $A$ or $B$, and those that end in $AA$ or $BB$. Express the numbers of strings of length $n+1$ of each of these types in terms of the numbers of length $n$.

Answer 2

I noticed it might help if you were to define the sequence $S_4$ in terms of $S_3$. For example, for defining $S_3$: $$S_3 = [A][S_2] + [B][S_2] + [C][S_3] - AAA - CCC - ABB - ABC - BAA - BAC = 21 - 6 = 15$$

I hoped this helped at all.

Answer 3

we have following cases for this string:

1..if the string starts with $C$ then the rest will be same as $S_{n-1}$.

2..if the string starts with $A$ the we have 2 subcases:

2.1.. if second one is $A$ meaning that string will start with $AA$, then next one has to be $C$ so we have $AAC$ as first three letter than the rest will be same as $S_{n-3}$

2.2.. if second one is $C$ meaning that string will start with $AC$, then the rest will be same as $S_{n-2}$.

3.. same argument holds for the case that string start with $B$.

As a result we have following recurrence:

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