Question

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

Answer 1

Answer:

The number of  palindromes is  

      $2^{\frac{n}{2} }$ when n is even and

      $2^{\frac{n +1}{2} }$ when n is odd

Step-by-step 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 $\frac{n}{2}$

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

       $p(n_{even }) = 2^{\frac{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 $\frac{n-1}{2}$

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

       $p(n_{odd }) =2^{\frac{n -1}{2} +1 } = 2^{\frac{n +1}{2} }$

Generally each bit could be either 0 or  1

Hence the number of  palindromes is  

      $2^{\frac{n}{2} }$ when n is even and

      $2^{\frac{n +1}{2} }$  when n is odd