Induction

General Induction Example 2



Problem: Prove that for an arbitrary string x of tex2html_wrap_inline30 , REV(REV(x)) = x.

Proof
First let us note that tex2html_wrap_inline30 can be defined recursively as follows:
Basis: tex2html_wrap_inline36 , where tex2html_wrap_inline38 is an empty string.
Induction: For arbitrary strings x of tex2html_wrap_inline30 and a of tex2html_wrap_inline46 , xa is also in tex2html_wrap_inline30 .
ExtremalClause: As usual. Omitted.

The proof mirrors the recursive definition of tex2html_wrap_inline30 .

Basis: Since tex2html_wrap_inline56 by the definition of REV ( click here to review the definition), tex2html_wrap_inline58 .
Induction: Assume that for an arbitrary string x of tex2html_wrap_inline30 REV(REV(x)) = x holds. -- Induction Hypothesis
Then for an arbitrary symbol a of tex2html_wrap_inline46 , REV(REV(xa)) = REV(a REV(x)) = REV(REV(x)) a by the definition of REV.
Then since by the induction hypothesis REV(REV(x)) = x, REV(REV(x)) = xa
Hence REV(REV(xa)) = xa.
End of Proof.