Question: 2017 Winter Final - 4
A bitstring $b_1b_2 \dots b_n$ is called a palindrome if $b_1b_2 \dots b_n = b_nb_{n-1} \dots b_1$, i.e.,
reading the string from left to right gives the same result as reading it from right to left. Let
$n \geq 3$ be an odd integer. How many palindromes of length $n$ are there?
(a)
$2^{n-1}$
(b)
$2^{n-2}$
(c)
$2^{(n+1)/2}$
(d)
$2^{(n-1)/2}$