Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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$). – Henning Makholm Sep 3 '11 at 22:01
up vote 3 down vote accepted

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.

share|cite|improve this answer
thanks, this cleared up a lot for me. – Hunter McMillen Sep 3 '11 at 23:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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