Recursive definition of a palindrome

Question

I have an alphabet $A =$ {0,1} and I want to find a recursive definition for the function $f(n)$ = {$v$: $v$ is a palindrome of length $n$ formed by characters of $A$}. I also want to find the size of this set (the number of palindromes of lenght $n$ formed by characters of $A$).

My thoughts are:

1. λ (empty word) is a palindrome.
2. For any $a_i$ ∈ $A$, $a_i$ is a palindrome.
3. If $v$ a palindrome and $a_i$ ∈ $A$, then $a_ika_i$ is a palindrome.

What would my recursive definition be and how can I find the number of palindromes?

Thanks.

Answer 1

A recursive definition of $f$ (for any alphabet $A$) should be something like this: $$f(n) = \begin{cases} \{\lambda\} &\mbox{if } n = 0 \\ A &\mbox{if } n = 1\\ \{ava : a \in A, v \in f(n - 2) \} &\mbox{if } n > 1 \end{cases}$$

Answer 2

This is a partial answer only concerned with the number of palindromes.

The number of palindromes of length 0 is 1. The number of palindromes of length 1 is 2 (namely 0, 1).

If $k$ is a palindrome of length $n$, then $0k0$ and $1k1$ are the only possible palindromes of length $n+2$, which doubles the number of palindromes from going from length $n$ to length $n+2$.

Thus, if we denote the number of palindromes of length $n$ by $g(n)$, we have $$g(n)=2g(n-2), \ n=2,\dots$$

For the exact number, we get different formulas for even and odd numbers: $$g(2k)=2^k\cdot g(0)=2^k, \quad g(2k+1)=2^k \cdot g(1)=2^{k+1}.$$