How many symmetrical strings of length $m$ can be formed using $n$ symbols?

Question

I'm having trouble trying to tackle this problem and need some help explaining the approach.

My task is this:

Given an alphabet with $n$ symbols, how many palindromes of length $m$ can be formed?

For instance if the alphabet is $\{a,b\}$ and $m=1,2,3$, you can make: $a,b, aa,bb, aaa,bbb,aba$ and $bab$.

Thanks in advance.

Answer 1

If $m=2k$ you just have to select the first $k$ elements freely, and this determines the other $k$. So there are $n^k$ palindromes.

If $m=2k+1$ you can select the first $k+1$ elements freely and this determines the other $k$. So there are $n^{k+1}$ palindromes.

Answer 2

Let $k(m)$ denote the number of palindromes of length $m$ that can be formed.

It's clear that $k(1) = n$, since every letter is a palindrome by itself. We also have $k(2) = n$, since only two copies of the same letter can form a palindrome of length $2$.

Then, for a palindrome of length $j$ > 2, what happens if you take off the first and last letter? You again have a palindrome. How many options are there for the first and last letter? How many options are there for the middle?