Question: 2017 Fall Midterm - 13
Consider strings of characters, where each character is $a$, $b$, or $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 strings of length $n$. Which of the following is true?
For any integer $n \geq 4$, let $B_n$ be the number of ccc-free strings 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}$