Suppose n is odd. Then n=2k+1.
A palindrome is entirely determined by the first k positions, as the last k must be the same in reverse. The middle position can be anything.
So we have 2 choices for the middle positions, and choices for the first k positions. So there are