Finding recurrence relation for strings of length n formed from A, B, C? 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!
 A: 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$.
A: 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}$
A: 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.
