3
$\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

$\endgroup$
1
  • $\begingroup$ 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$). $\endgroup$ – hmakholm left over Monica Sep 3 '11 at 22:01
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thanks, this cleared up a lot for me. $\endgroup$ – Hunter McMillen Sep 3 '11 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.