Question: 2017 Winter Final - 5
Let $n \geq 2$ be an integer. What does $2^{n} - 2^{n-2}$ count?
(a)
The number of bitstrings of length $n$ in which the first bit is equal to the last bit.
(b)
The number of bitstrings of length $n$ in which the first bit is 0 or the last bit is 1.
(c)
The number of bitstrings of length $n$ in which the first bit is not equal to the last bit.
(d)
The number of bitstrings of length $n$ in which the first bit is 0 and the last bit is 1.