I'm practicing proofs and given the following statement:
Let $\Sigma$ be an alphabet, $\epsilon$ the empty word and $\sigma:\Sigma^{*}\rightarrow\Sigma^{*}$ an operation which for $a\in\Sigma$ and $w\in\Sigma^{*}$ is defined as $$\sigma(\epsilon)=\epsilon,\\\sigma(wa)=a\sigma(w).$$
I would like to prove through induction that $\sigma$ is equal to the word reversal operation $rev$ meaning that $\sigma(w)=rev(w)=w_{n}...w_{1}$ for every $w=w_{1}...w_{n}\in\Sigma^{*}$.
My suggestion is as follows:
For $w=\epsilon$ we have $$\sigma(w)=\sigma(\epsilon)=\epsilon=rev(\epsilon)=rev(w).$$
Let $w=xa$ with $x\in\Sigma^{*}$ and $a\in\Sigma$, then $$\sigma(x)=x_{n}...x_{1}=rev(x).$$
Thus we also have $$\sigma(w)=\sigma(xa)=\sigma(x_{1}...x_{n}a)=a\sigma(x_{1}...x_{n})=ax_{n}\sigma(x_{1}...x_{n-1})=...=ax_n...x_{1}=rev(x_{1}...x_{n}a)=rev(xa)=rev(w).$$
Does that constitute a correct and sufficient proof? If not, I would very much appreciate your feedback.
You're close.
The basis case is ok. The problem is with the final line. It's an expansion of the reversal definition for each character. So while it is correct for any individual string, it implies that the whole proof for all strings is infinite in length, which is disallowed.
The problem is fixed by using the inductive hypothesis which the induction axiom gives us. So we are allowed to simply assume the relationship works for all strings of length $k$; if we can prove that the same relationship holds for all strings of length $k+1$ (and have a correct proof of the basis case), we can then conclude the relationship holds for all strings of any length.
For the induction step of this proof, the induction hypothesis is $\sigma(x) = rev(x)$, so
$$ \sigma(w) = \sigma(x a) = a \sigma(x) = a\:rev(x) = rev(w) $$