To form a palindrome, you can fill anything you want for the first half of the string and in the second half you need to repeat what you filled in first half in reverse manner.
In case n is odd, there will be a middle element in which you can fill anything as this will always stay in middle when you reverse the string as well.
When n is even:
No of ways the first half of string can be filled = 2^(n/2)
No of ways to fill second half = 1 (since you have to repeat first half)
So no of palindromes = 2^(n/2) * 1 = 2^(n/2)
When n is odd:
No of ways the first half of string can be filled = 2^((n - 1)/2)
No of ways to fill middle bit = 2
No of ways to fill second half = 1 (since you have to repeat first half)
So no of palindromes = 2^((n - 1)/2) * 2 * 1 = 2^((n+1)/2)
Hope this helps!
