Solution: 2018 Winter 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} + 1$

(b)

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

(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

Let’s write out the possibilities and sum them:

$ 1, S_{n-1} $ is not allowed since this would mean the recursive call's next value could also be 1, which leads to 11
$ 0, S_{n-1} $
$ 1, 0, S_{n-2} $

Although this takes into account many possibilities, it does not take into a bitstring that is made of all 1’s: 1

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