[Math] 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}$$