Solution: 2019 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

Let’s sum all possible recursive functions:

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

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