Recursive definition of a palindrome 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.

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}$$