Solution: 2015 Fall Midterm - 4

Author: Michiel Smid

Question

For any integer $n \geq 2$, let $S_n$ be the number of bitstrings of length $n$ in which the first bit is not equal to the last bit. Which of the following is true?

(a)

$S_n = 2^{n} - 2^{n-1} + 2^{n-2}$

(b)

$S_n = 2^{n} - 2^{n-2}$

(c)

$S_n = 2^{n-2}$

(d)

$S_n = 2^{n-1}$

Solution

So the first bit can be 1 or 0: 2 possibilities

The last bit has to be the opposite of the first bit: 1 possibility

The remaining n-2 bits can be anything: $2^{n-2}$ possibilities

Thus, the number of bitstrings is $2 \cdot 1 \cdot 2^{n-2} = 2^{n-1}$