Question: 2015 Fall Midterm - 4
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}$
(c)
$S_n = 2^{n} - 2^{n-2}$
(d)
$S_n = 2^{n-1}$