Prove that if $z^n$ is a palindrome for some $n>0$, then $z$ is also a palindrome for any alphabet E.

Question

Prove that if $z^n$ is a palindrome for some $n>0$, then $z$ is also a palindrome for any alphabet E.

Here's a proof of the statement above:

Let $w = x^n$. If $n = 1$, then the result is trivial.
Suppose $n > 1$. Then $$x^n = reverse (x^n) = (reverse (x))^n.$$ Write this as $$x x \dots x = reverse (x) reverse (x) \dots reverse (x).$$ But $x$ and $reverse (x)$ have the same length, so that $x = reverse (x)$.

Can anyone justify this line in the proof? $$reverse (x^n) = (reverse (x))^n$$

Or provide an alternative proof.

Answer 1

A simple argument proves the statement. Essentially, it proves explicitly that $\text{rev}(z^n) = (\text{rev}(z))^n$ (if you assume it, there is nothing to prove).

Before showing the argument, some preliminaries. Any word can be written as $z = z_1 \dots z_k$, where $k \geq 0$ is the length of $z$ and the $z_i$'s are single characters of any alphabet $E$. A word $z = z_1 \dots z_k$ is palindrome if $z = \text{rev}(z)$ where $\text{rev}(z) = z_k \dots z_1$.

Now, let us see the proof. The hypothesis in the statement says that, for some $n > 0$, we have $z^n = \text{rev}(z^n)$. Written more explicitly, for $z = z_1 \dots z_k$, we have

\begin{align} z^n &= \overbrace{\overbrace{z_1 \dots z_k}^z \ \cdots \ \overbrace{z_1 \dots z_k}^z}^{n \text{ times}} \\ &= \\ \text{rev}(z^n) &= z_k \dots z_1 \ \cdots \ z_k \dots z_1 \end{align}

(Note that the first occurrence of $z_k$ in $\text{rev}(z^n)$ corresponds to the last occurrence of $z_k$ in $z^n$; and the first occurrence of $z_{k-1}$ in $\text{rev}(z^n)$ corresponds to the last occurrence of $z_{k-1}$ in $z^n$; and so on. This is the way to construct $\text{rev}(z^n)$ from $z^n$.)

Since $n > 0$, the identity $z^n = \text{rev}(z^n)$ holds in particular for the first $k$ characters of $z^n$ and $\text{rev}(z^n)$, hence \begin{align} z = z_1 \dots z_k = z_k \dots z_1 = \text{rev}(z) \end{align} Therefore, $z$ is palindrome.

---

Note that we have not assumed that $\text{rev}(z^n) = (\text{rev}(z))^n$. Actually, the fact that $\text{rev}(z^n) = (\text{rev}(z))^n$ is an immediate consequence of what we have proved.

Answer 2

$$\begin{array}{rcl} z^k \in \text{Palindrome} &\implies& z^k = \text{rev}(z^k) \\ &\implies& z^k{}_1 = z^k{}_{kn}~,~z^k{}_2 = z^k{}_{kn-1}~,~z^k{}_3 = z^k{}_{kn-2}~,~\dots \\ &\implies& z_1 = z_n~,~z_2 = z_{n-1}~,~z_3 = z_{n-2}~,~\dots \\ &\implies& z \in \text{Palindrome} \end{array}$$

Third line follows from $z^k{}_{a} = z_{a ~\rm{mod}~ n}$