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