Kenneth Rosen Edition 7 Exercise 6.1 Question 41 (Page No. 397)

Question

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

Answer 1

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

APPROACH: 

for even length strings:

1^st bit and nth bit are same. similarly, 2^nd 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}$.