2
$\begingroup$

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

  • 0
    Instead of doing induction over the entire $|uv|$, let the induction variable be just $|v|$ and keep the $u$ constant-but-arbitrary throughout the induction proof. (Also, since $u$ can be empty, the base case should probably be $|u|=0$ rather than $|u|=1$).2011-09-03

1 Answers 1

3

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.

  • 0
    thanks, this cleared up a lot for me.2011-09-03