Question: 2018 Fall Midterm - 9
A bitstring $s_1s_2...s_n$ is called a palindrome, if $$s_1s_2...s_{n-1}s_n = s_ns_{n-1}...s_2s_1,$$
i.e., reading the string from left to right gives the same string as when reading from right to left.
For any integer $n \geq 1$, let $P_n$ be the number of bitstrings of length $n$ that are palindromes.
Which of the following is true for any integer $n \geq 3$?
For any integer $n \geq 1$, let $P_n$ be the number of bitstrings of length $n$ that are palindromes.
Which of the following is true for any integer $n \geq 3$?
(a)
$P_n = 2 \cdot P_{n/2}$
(b)
$P_n = 2 + P_{n-2}$
(c)
$P_n = 2 \cdot P_{n-2}$
(d)
$P_n = 2 \cdot P_{n-1}$