You are correct for when n is even.

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