This problem is taken from "Mathematics for Computer Science" (Lehman, Leighton, Meyers, 2018).
1. Definitions
First, some relevant definitions.
1.1. String
The set $A^*$ of strings over alphabet $A$ is defined as follows:
Base case: the empty string $\lambda$ is in $A^*$.
Constructor case: If $a\in A$ and $s\in A^*$, then the pair $\langle a,s\rangle\in A^*$.
1.2. String reversal
The string reversal function, $\text{rev} : A^* \rightarrow A^*$ has a recursive definition.
Base case: $\text{rev}(\lambda):=\lambda$
Constructor case: $\text{rev}(as):=\text{rev}(s)a$ for $s\in A^*$ and $a\in A$.
Also, the following facts about string concatenation will be used without proof:
$(rs = uv \text{ AND } |r|=|u|) \text{ iff } (r=u\text{ AND }s=v)$
$r\cdot (s\cdot t) = (r\cdot s)\cdot t$
1.3. Palindrome
A string is a palindrome when $\text{rev}(s) = s$. The palindromes also have a simple recursive definition as the set $\text{RecPal}$.
Base cases: $\lambda\in \text{RecPal}$ and $a\in \text{RecPal}$ for $a\in A$.
Constructor case: If $s\in \text{RecPal}$, then $asa\in \text{RecPal}$ for $a\in A$.
2. Problem
Prove that if $s = \text{rev}(s)$, then $s\in \text{RecPal}$.
3. Solution
The proof is by strong induction on $n=|s|$ (the length of the string $s$).
Induction hypothesis: $P(n) := \text{for all }s \in A^*,\text{ if }|s| = n\text{ AND }s = \text{rev}(s),\text{ then }s\in \text{RecPal}$.
Base cases:
($n = 0$): In this case, $s = \lambda$, and $s = \text{rev}(s) = \lambda$ (by definition of $\text{rev}$). Also, $s=\lambda\in\text{RecPal}$, by definition of $\text{RecPal}$.
($n = 1$): In this case, $s = a$, and $s=\text{rev}(s)=a$, and $a \in \text{RecPal}$.
Induction step: Assume $s$ is a string such that $s = \text{rev}(s)$ and $|s| = n + 1$ for some $n \geq 1$.
Since $s = rev(s)$, then $s = ata$ for some $t\in A^*$. Proof: By contradiction. Assume $s = atb$ for some $a,b\in A$ and $t\in A^*$, with $a \neq b$. Then, $\text{rev}(s) = \text{rev}(tb)a = (b\cdot rev(t))\cdot a$, so $s \neq \text{rev}(s)$, which is a contradiction.
Then:
$ata = \text{rev}(ata) = \text{rev}(ta)a = a\cdot\text{rev}(t)\cdot a$
Stripping the final $a$ from both sides:
$at = a\cdot\text{rev}(t)$
By the fact listed under the String reversal section ($(rs = uv \text{ AND } |r|=|u|) \text{ iff } (r=u\text{ AND }s=v)$), since $|a| = |a|$, then $t = \text{rev}(t)$.
Since $t = \text{rev}(t)$ and $|t| = n - 1$, by the induction hypothesis $P(n - 1)$, $t\in\text{RecPal}$.
So, by the constructor case of $\text{RecPal}$, it follows that $s = ata\in\text{RecPal}$.
This proves $P(n + 1)$.
Therefore, by strong induction, $P(n)$ is true for all $n\geq 0$.
Can someone please verify if this solution is correct?