Tell me more ×
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.
up vote 0 down vote favorite

I am trying to inductively prove that for any string s, the reverse of the reverse of string s is string s.

share|improve this question
5  
I am sorry to hear that, because that sounds like a heavy-handed approach to something which is really obvious: the reverse of $a_1 \cdots a_n$ is $a_n \cdots a_1$ and the reverse of that is of course $a_1 \cdots a_n$. Note though that you have not asked a question. – Pete L. Clark Mar 23 '11 at 5:38
2  
It could be to help familiarize the OP with induction. – Alex Becker♦ Mar 23 '11 at 6:01
What is your inductive definition of "string reversal" ? – chandok Mar 23 '11 at 12:46

1 Answer

up vote 4 down vote

The case $n = 1$ is trivial. For $n > 1$, assume that the statement holds for all $i < n$. Let $s = as'$ be a string of length $n$ where $a$ has length 1 and $s'$ has length $n - 1$. The key is to observe that rev($ab$) = rev($b$)rev($a$). Therefore rev(rev($s$)) = rev(rev($as'$)) = rev(rev($s'$)rev($a$)) = rev(rev($a$))rev(rev($s'$)) = $as'$ = $s$, thus the statement holds for strings of length $n$. We have now proved by induction that the reverse of the reverse of a string $s$ is $s$.

share|improve this answer

Your Answer

 
discard

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