126 views
A palindrome is a string whose reversal is identical to the string. How many bit strings of length $n$ are palindromes?

Ans: $2^{\lceil n/2 \rceil}$

APPROACH:

for even length strings:

1st bit and nth bit are same. similarly, 2nd and (n-1)th bits are same.
Now, 2 bits for every position, and we are filling n/2 positions. therefore $2^{n/2}$ strings

for odd-length strings

1st bit and nth bit are same. similarly, 2nd and (n-1)th bits are same. but {(n+1)/2}th positions has 2 more ways to be filled
Now, 2 bits for every position, and we are filling n/2 positions. therefore $2^{n+1/2}$ strings.

We can also write it as $2^{\lceil n/2 \rceil}$.