Induction – How to Prove Reversal of a String by Induction

induction

I am trying to prove that:

(uv)R = vRuR

where R is the reversal of a String defined recursively as:

aR = a

(wa)R = awR

I think I have the base case right, but I am having trouble with the inductive step and final proof.

here is what I have:

Base Step

prove for n = 1 where |uv| = 1

(uv)R = uReR = uR = u (where e is the empty string)

I dont really know where to go from here, any help would be great.

Thanks

Best Answer

I agree with Henning that your induction should be on $|v|$. Note in the case $|v| = 1$, you're done by definition. It's probably also worth mentioning something about the empty string for completeness.

Let me demonstrate how I would prove this for $|v| = 3$ supposing we knew this were true for when $|v| = 2$. This should illustrate how you should prove $|v| = n$ from assuming $|v| = n - 1$ is valid.

Let $v = v_1v_2v_3$ be a string of length 3. Assume the claim is true for strings of length 2. Then $(uv)^R = (uv_1v_2v_3)^R$. By the recursive definition, $(uv_1v_2v_3)^R = v_3(uv_1v_2)^R$. Note $v_1v_2$ is a string of length 2, so we have $v_3(uv_1v_2)^R = v_3(v_1v_2)^Ru^R$. But by definition, $v_3(v_1v_2)^Ru^R = v_3v_2v_1u^R = (v_1v_2v_3)^Ru^R$.

In almost all inductive proofs, it helps to prove a few small cases by using even smaller cases. If you're still having trouble, try proving this for $|v| = 4$ by using the same ideas as above.

Related Question