Solution: 2017 Winter Final - 8

Author: Michiel Smid

Question

Consider bitstrings that contain at least one occurrence of 000. Let $S_n$ be the number of such strings having length $n$. Which of the following is true for $n \geq 4$?

(a)

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

(b)

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

(c)

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

(d)

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

Solution

Consider the case where the current bit, next bit, and bit after that are all 0

That means we can just calculate the remaining possible bitstring combinations since the requirements have already been met

$ 2^{n-3} $

$ 1, S_{n-1} $

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

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

Adding them up, we get $ S_n = S_{n-1} + S_{n-2} + S_{n-3} + 2^{n-3} $