Set of palindromes with induction Let $A = \{a_1, a_2, ..., a_k\}$ be a finite alphabet. 
a. Define, using structural induction, set of all palindromes of A. 
b. Find the recurrent pattern which represents the number of all palindromes for length n,  where $n = 1,2, \ldots $
Any hints please I am lost?
 A: For a definition by structural induction you need base cases and one or more rules for building ‘new’ palindromes from old ‘ones’. It’s often helpful to work backwards first: if $w=x_1x_2\ldots x_n$ is a palindrome, what can we say about $x_n$? It must be the same as $x_1$. And what happens if we remove those two matched symbols? We’re left with $x_2\ldots x_{n-1}$, which must be a shorter palindrome. (It may of course be the empty word, but that’s a palindrome: after all, it’s certainly equal to its reversal!)
This procedure of stripping off the end symbols must eventually reduce $w$ to the empty word or to a palindrome of length $1$. Conversely, any palindrome can be built up from the empty word or a palindrome of length $1$ by repeatedly adding identical symbols at both ends. For example, if our alphabet is $\{a,b,c\}$, the palindrome $abaccaba$ strips down to the empty word ($\epsilon$): 
$$abaccaba\to baccab\to acca\to cc\to\epsilon$$
Reversing the process allows us to generate it from the empty word
$$\epsilon\to cc\to acca\to baccab\to abaccaba$$
by successively adding $c,a,b$, and $a$ at front an back. And we now have everything that we need: the base cases are the empty word and the one-symbol words, and the ‘new-from-old’ rule is that we may surround a palindrome by a pair of identical symbols.

Let $P$ be the set of palindromes over $A$.
  
  
*
  
*$\epsilon,a_1,a_2,\ldots,a_k\in P$.  
  
*If $w\in P$, then $awa\in P$ for each $a\in A$.  
  
*A word $w\in A^*$ belongs to $p$ if and only if is listed in (1) or can be obtained from a palindrome in (1) by some finite number of applications of (2).
  

Once you have this definition, you can use it to count the palindromes of length $n$: it’s pretty clear that if there are $p_n$ palindromes of length $n$, (2) gives you $kp_n$ palindromes of length $n+2$: $p_{n+2}=kp_n$. Starting with $p_0=1$, this gives you a recurrence for palindromes of even length; starting with $p_1=k$, it gives you one for palindromes of odd length. These recurrences come directly from the definition: $p_0$ and $p_1$ come from (1), and the recurrences themselves come from (2). These are simple recurrences that are easily solved.
However, there is another way to get at $p_n$ that may be easier: just notice that a palindrome of length $2n$ is completely determined by its first $n$ symbols, while a palindrome of length $2n+1$ is completely determined by its first $n+1$ symbols, and in each case that initial substring can be any word over $A$ whatsoever.
A: Palindromes with 1 digit (A) have "k" possibilities for that digit
Palindromes with 2 digits (AA) have "k" possibilities for those two digits
Palindromes with 3 digits (ABA) have "k" possibilities for the 1st and 3rd digits * "k" possibilities for the 2nd digit = $k^2$
Palindromes with 4 digits (ABBA) have "k" possibilities for the 1st and 4th digits * "k" possibilities for the 2nd and 3rd digits = $k^2$
Palindromes with 5 digits (ABCBA) have "k" possibilities for the 1st and 5th digits * "k" possibilities for the 2nd and 4th digits * "k" possibilities for the 3rd digit = $k^3$
…
Continuing the pattern we see that
1) palindromes with an odd number of "n" digits with have $k^{\frac{n+1}{2}}$ combinations, and 
2) palindromes with an even number of "n" digits will have $k^{\frac{n}{2}}$ combinations
A: Structural induction is a very complicated way to define something.  You generally want to avoid it.  There are only 2 ways (in sequential logic) to define an inductive set:


*

*define it using an inductive axiom

*define it in terms of some other set that itself is inductive, such as integers or lists or trees


To actually define a set inductively, you have to use the first technique, even though the second approach is much easier.  To define your set using the first technique, you need a base case and an extension.  Define the extension function:
$$E(s) = \{a_0 . s . a_0 ~,~ a_1 . s . a_1 ~,~ \dots ~,~ a_k . s . a_k \}$$
(where $.$ is string concatenation).  But that isn't the definition of a set, that is just a function.  To use this to defin a set, you need 3 things: base case, extension case, and inductive assumption.
(1) Base case
$$\DeclareMathOperator{\Pali}{\text{Palindromes}} \epsilon \in \Pali$$
(2) Extension case
$$s \in \Pali \Rightarrow E(s) \in \Pali$$
So far we have declared that everything we would consider a palindrome is a member of the set $\Pali$.  But we haven't declared that everything else isn't a palindrome.  To do this, you need induction:
(3) Inductive assumption for any predicate $P$:
$$\begin{gather}
P(\epsilon) \text{ and } \bigg(\forall s \in \Pali \Rightarrow \forall s' \in E(s) ~:~ P(s')\bigg) \\
 \downarrow \\
 \bigg(\forall s \in \Pali ~:~ P(s)\bigg)
\end{gather}$$
With the 3rd equation you can actually prove things like $"12" \not \in \Pali$ by using an appropriate choice of $P$.

As I said , the easy way is to define the set of palindromes in terms of another already inductively defined set.  For example, in terms of integers:
$$D(n) = \text{n}^{\text{th}}\text{ palindrome in lexicographical order}$$
$$\Pali = \{D(n) ~:~ n \in \mathbb N\}$$

Or they can be defined in terms of the inductive set of all lists over $A$:
$$\Pali = \{L ~:~ L \in A^* \text{ and } L_{k} = L_{|L| + 1 - k}\}$$

Part (B)
Any (nonempty) string can be used to create at least 2 palindromes.  Example:
$$\text{ABCD becomes ABCDCDBA or ABCDDCBA}$$
More importantly, the process can be reversed.  Used this to count the number of even length palindromes and odd length palindromes.
