Please explain: For any integer $n \ge 4$, let $B_n$ be the number of ccc-free bitstrings of length $n$. Which of the following is true?

Question

Consider strings of characters, where each character is an element of the set $\{a, b, c\}$. Such a string is called ccc-free, if it does not contain ccc.

For any integer $n \ge 4$, let $B_n$ be the number of ccc-free bitstrings of length $n$. Which of the following is true?

I know the answer is $B_n = 2·B_{n−1} +2·B_{n−2} +2·B_n$, but I don't understand how to get to that answer.

Answer 1

Let $B_n$ be the number of $ccc$-free strings of length $n$ from the alphabet $\{a,b,c\}$.

For $0 \le n \le 2$, we have $$B_0=1,\;\;B_1=3,\;\;B_2=9$$ Next, suppose $n \ge 3$.

Then a $ccc$-free string of length $n$ has exactly one of the $6$ forms

• $aX$$\\[4pt]$
• $bX$$\\[4pt]$
• $caY$$\\[4pt]$
• $cbY$$\\[4pt]$
• $ccaZ$$\\[4pt]$
• $ccbZ$

where $X,Y,Z$ are $ccc$-free strings of lengths $n-1,n-2,n-3$ respectively, but otherwise arbitrary.

There are

• $B_{n-1}$ choices for $X$.$\\[4pt]$
• $B_{n-2}$ choices for $Y$.$\\[4pt]$
• $B_{n-3}$ choices for $Z$.$\\[4pt]$

hence, summing the counts for each of the $6$ forms, we get $$B_n = 2B_{n-1} + 2B_{n-2} + 2B_{n-3}$$

Incorporating the initial values, we get $$ B_n = \begin{cases} 1,\;\text{if}\;n=0\\ 3,\;\text{if}\;n=1\\ 9,\;\text{if}\;n=2\\ 2B_{n-1} + 2B_{n-2} + 2B_{n-3},\;\text{if}\;n\ge 3\\ \end{cases} $$