Solution: 2016 Fall Midterm - 4

Author: Michiel Smid

Question

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

Solution

There are 6 possibilities for the first 3 bits.

We can also get 6 possibilities by taking all 8 possible 3 bit combinations and subtracting the 2 possibilities where all 3 bits are the same.

For all other bits, there are 2 possibilities.

Thus, there are $6 \cdot 2^{n-3}$ bitstrings.