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$?
(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}$
Solution
We can check all possibilities and sum them up.
The current left and right bits are fixed, so the possibilities on the {n-2} bits will be called on $ P_{n-2} $