Set of palindromes with induction

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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

1. $\epsilon,a_1,a_2,\ldots,a_k\in P$.
2. If $w\in P$, then $awa\in P$ for each $a\in A$.
3. 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.