Practice By Tag: COMP 2804: Discrete Structures II

Question: 2019 Winter Final - 9

1 . Consider bitstrings that do not contain 011 and have 1 at every even position. (The positions are numbered $1,2,3,...$). Let $S_n$ be the number of such strings having length $n$. Which of the following is true for any $n \geq 3$?

(a)

$S_n = 1 + S_{n - 1}$

(b)

$S_n = S_{n - 1} + S_{n - 3}$

(c)

$S_n = 1 + S_{n - 2}$

(d)

$S_n = S_{n - 2} + S_{n - 3}$