Question: 2014 Fall Midterm - 11

Author: Michiel Smid

Let $B_n$ be the number of bitstrings of length $n$ that do not contain 1111. Which of the following is true?

a) $B_n = B_{n-1} + B_{n-2} + B_{n-3}$

b) $B_n = B_{n-1} + B_{n-2} + B_{n-3} + B_{n-4}$

c) $B_n = 2^{n} - 2^{n-4}$

d) $B_n = 2^{n} - (n-3) \cdot 2^{n-4}$

Let $B_n$ be the number of bitstrings of length $n$ that do not contain 1111. Which of the following is true?

(a)

$B_n = 2^{n} - (n-3) \cdot 2^{n-4}$

(b)

$B_n = 2^{n} - 2^{n-4}$

(c)

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

(d)

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