Solution: 2017 Fall Midterm - 13

Author: Michiel Smid

Question

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?

(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}$

Solution

We can write down some possibilities first.

$ a, B_{n-1}$ possibilities left

$ b, B_{n-1}$ possibilities left

$ c,a, B_{n-2}$ possibilities left

$ c,b, B_{n-2}$ possibilities left

$ c,c, a, B_{n-3}$ possibilities left

$ c,c, b, B_{n-3}$ possibilities left

$ B_n = B_{n-1} + B{n-1} + B_{n-2} + B_{n-2} + B_{n-3} + B_{n-3} $

$ B_n = 2B_{n-1} + 2B_{n-2} + 2B_{n-3} $