Solution: 2018 Fall Midterm - 9

Author: Michiel Smid

Question

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} $

$ 0, P_{n-2}, 0 $

$ 1, P_{n-2}, 1 $

$ P_n = P_{n-2} + P_{n-2} $

$ P_n = 2P_{n-2} $