Prove by inductive on the length of u

Question

I have this question:

Let u be a string, Prove by inductive on the length of u, that (u^R)^R = u "where R indicates reversal"

I tried answer this question by this way:

Basis step: u = 0 then (u^R)^R = 0

Could someone help me in inductive step

thanks

Answer 1

$$\DeclareMathOperator{\Rev}{Rev} \DeclareMathOperator{\First}{First} \DeclareMathOperator{\Rest}{Rest}$$

Ah, this is actually a classic "Formal Logic" question, that

$$\Rev( \Rev(L)) = L \tag{A1}$$

It is not a problem someone who is just learning induction should attempt. But if you are already familiar with induction, here presents the standard approach.

In order to prove this statement inductively, you need a recursive definition for $\Rev$. Let's use the definition:

$$\Rev(L) = \Rev(\Rest(L))~.~\First(L) \tag{A2} $$

Where

• $\First$ is the first character of a string
• $\Rest$ is all but the first character of a string
• $~.~$ is string concatenation

Then apply the definition to (A1):

$$\Rev\bigg(\Rev(\Rest(L))~.~\First(L)\bigg) = L \tag{A3}$$

So we need a lemma:

$$\Rev(A~.~B) = \Rev(B)~.~\Rev(A) \tag{A4}$$

Applying the lemma to (A3)

$$\Rev(\First(L))~.~\Rev(\Rev(\Rest(L))) = L \tag{A5}$$

Now notice that $\First(L)$ is only $1$ character long. So $\Rev(\First(L)) = \First(L)$.

Also notice that $\Rest(L)$ is shorter than $L$. So by an inductive hypothesis, $\Rev(\Rev(\Rest(L))) = \Rest(L)$

Applying the prior 2 statements to (A5):

$$\First(L)~.~\Rest(L) = L \tag{A6}$$

Which is true.