1. ## Palindrome

A palindrome is a string which, when reversed it is identical to the original string, eg. 0110 is a palindrome and 0100 is not. How many bit strings of length n are palindromes?

I would really appreciate any help.

2. Originally Posted by sana07
A palindrome is a string which, when reversed it is identical to the original string, eg. 0110 is a palindrome and 0100 is not. How many bit strings of length n are palindromes?

I would really appreciate any help.
n even:

Spilt the string in half. The first n/2 characters can be either 0 or 1 so there are $\displaystyle 2^{n/2}$ arrangements. You require the second half to be the reverse of the first half and there's only 1 way that can happen. Therefore ....

n odd:

The middle character can be 0 or 1 so there's 2 possibilities for the middle.
The characters to the left of the middle character can be either 0 or 1 so there's $\displaystyle 2^{(n-1)/2}$ arrangements. You require the characters to the right of the middle character to be the reverse of the characters to the left and there's only 1 way that can happen. Therefore ....