Solution: 2019 Fall Final - 9

Author: Michiel Smid

Question

Consider bitstrings that do not contain 110. Let $S_n$ be the number of such strings having length $n$. Which of the following is true for any $n \geq 4$?

(a)

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

(b)

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

(c)

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

(d)

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

Solution

Warning: I suck at these questions. Here goes nothing

Possibilities:

$0, S_{n-1}$

$1,0, S_{n-2}$

IDK MAN