Question: 2018 Winter Midterm - 13
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 \geq 4$, let $B_n$ be the number of ccc-free bitstrings of length $n$. Which of the following is true?
For any integer $n \geq 4$, let $B_n$ be the number of ccc-free bitstrings of length $n$. Which of the following is true?
(a)
$B_n = B_{n-1} + B_{n-2} + 2 \cdot B_{n-3}$
(b)
$B_n = 2 \cdot B_{n-1} + 2 \cdot B_{n-2} + 2 \cdot B_{n-3}$
(c)
$B_n = B_{n-1} + B_{n-2} + B_{n-3}$
(d)
$B_n = 2 \cdot B_{n-1} + 2 \cdot B_{n-2} + B_{n-3}$