Question: 2019 Fall Midterm - 4
For any integer $n \geq 3$, let $B_n$ be the number of bitstrings of length $n$ in which the first
three bits are not all equal. Which of the following is true?
(a)
$B_n = 2^n - 6$
(b)
$B_n = 2^n - 2$
(c)
$B_n = 2 \cdot 2^{n - 3}$
(d)
$B_n = 6 \cdot 2^{n - 3}$