Back

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}$

Solution: 2014 Fall Midterm - 11

Author: Michiel Smid

Question

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_{n-4}$
(b)
$B_n = 2^{n} - (n-3) \cdot 2^{n-4}$
(c)
$B_n = B_{n-1} + B_{n-2} + B_{n-3}$
(d)
$B_n = 2^{n} - 2^{n-4}$

Solution

There are 4 possibilities every time.

It can go as follows without getting 4 consecutive 1s $…$

0 $B_{n-1}$

1 0 $B_{n-2}$

1 1 0 $B_{n-3}$

1 1 1 0 $B_{n-4}$

We have the following amount of recursive possibilities: $B_{n-1}+B_{n-2}+B_{n-3}+B_{n-4}$