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!
Best Answer
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$.