The reverse of a string is given as $rev(x)$ for any string $x$. For example, $rev(abcdefg) = gfedcba$.
The problem is as follows:
Prove, using induction on the length of the string, that $rev(rev(s)) = s$ (read: "the reverse of the reverse of a string $s$ is $s$") for any string $s \in \Sigma^*$.
My inductive proof is as follows:
Basis: For $|s| = 0$, $s = \epsilon$. Therefore, $rev(rev(\epsilon)) = rev(\epsilon) = \epsilon$.
Hypothesis: Assume $rev(rev(s)) = s$ is true for $|s| = k$, where $k \ge 1$.
Inductive Step: Show that $rev(rev(s)) = s$ is true for $|s| = k + 1$.
From the assumption that $rev(rev(s)) = s$ is true for a string $s$ of length $k$, the statement must be true for another string $s$ of length $k + 1$.
I would like to know whether my proof suffices. Did I make any mistakes on evaluating after the inductive step?
The basis is correct, but the hypothesis and inductive step need to be strengthened:
Hypothesis: Assume $rev(rev(s))=s$ is true for any $|s|=k$, where $k\ge1$.
Inductive Step: Show that $rev(rev(s))=s$ is true for any $s$ such that $|s|=k+1$.
From the assumption that $rev(rev(s))=s$ is true for all strings $s$ of length $k$, the statement must be true for all strings $s$ of length $k+1$.