Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|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
add comment

1 Answer

up vote 2 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|improve this answer
    
thanks, this cleared up a lot for me. –  Hunter McMillen Sep 3 '11 at 23:08
add comment

Your Answer

 
discard

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.