Solution: 2015 Fall Final - 10

Author: Michiel Smid

Question

What is the number of bitstrings of length $n$ that contain 00 or 11?

(a)

$2 \cdot n \cdot 2^{n-1}$

(b)

$2^n - 2$

(c)

$2^n - 4$

(d)

$2 \cdot (n-1) \cdot 2^{n-2}$

Let S be the set of all bitstrings of length $n$.
$ |S| = 2^{n} $
Let A be the event that a string does not contain 00 or 11.
The strings are only $1010...10$ or $0101...01$.
$ |A| = 2 $

Now, we exclude the strings that do not contain 00 or 11

$ |S| - |A| = 2^{n} - 2 $