I am trying to inductively prove that for any string s, the reverse of the reverse of string s is string s.
Inductive Proof of String Reversal
2
$\begingroup$
logic
-
0What is your inductive definition of "string reversal" ? – 2011-03-23
1 Answers
5
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$.