Question

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

Answer 1

The number of palindromes is

`2^{(n)/(2) }` when n is even and

`2^{(n +1)/(2)  }` when n is odd

Explanation:

From the question we are told that

The length of the string is
`n`

Generally palindrome is evaluated by considering the first part of a string

When the the length of the string is an even number then

it means that the first part of the string is
`(n)/(2)`

Hence the number of bit strings of length n that are palindromes is evaluated as

`p(n_(even )) =  2^{(n)/(2) }`

But When the the length of the string is an odd number then

it means that the first part of the string is
`(n-1)/(2)`

Hence the number of bit strings of length n that are palindromes is evaluated as

`p(n_(odd )) =2^{(n -1)/(2) +1 } = 2^{(n +1)/(2)  }`

Generally each bit could be either 0 or 1

Hence the number of palindromes is

`2^{(n)/(2) }` when n is even and

`2^{(n +1)/(2)  }` when n is odd