Practice By Tag: COMP 2804: Discrete Structures II

Question: 2015 Fall Midterm - 4

1 . 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-2}$

(b)

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

(c)

$S_n = 2^{n-2}$

(d)

$S_n = 2^{n-1}$