Solution: 2016 Fall Midterm - 11

Author: Michiel Smid

Question

For any integer $n \geq 1$, let $B_n$ be the number of bitstrings of length $n$ that do not contain the substring 11 and do not contain the substring 101. Which of the following is true for any $n \geq 4$?

(a)

$B_n = B_{n - 2} + B_{n - 4}$

(b)

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

(c)

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

(d)

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

Solution

We can write down some possibilities first.

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

$ 0, 0, 1, B_{n-3}$ possibilities left

Thus, there are $ B_n = B_{n-1} + B_{n-3}$ possibilities.