Induction
Basis Step: Prove that P(x) is true for all the elements x in the basis of S.
Induction: Prove that
for any element(s) x of S
if P(x) is true, then
P(y) is true for any element y obtained from x by the induction step of
the recursive definition of S.
As a first step for this proof it is often a good idea to express y in terms of x
so that P(x) can be used.
Example 1
Prove that for arbitrary strings x and y of
REV(xy) = REV(y) REV(x) holds.
To see the recursive definition of REV
Proof
First let us note that can be defined recursively as follows:
Basis: , where is an empty string.
Induction: For arbitrary strings x of and a of ,
xa is also in .
ExtremalClause: As usual. Omitted.
The proof of the equality in question is going to be proven for an arbitrary fixed x by induction on y. Thus the statement to be proven is for an arbitrary fixed string x, and an arbitrary string y of , REV(xy) = REV(y) REV(x) holds. The proof mirrors the recursive definition of .
Basis: .
Induction: Assume that for an arbitrary string y of ,
REV(xy) = REV(y) REV(x) holds. -- Induction Hypothesis
Then for an arbitrary symbol a of ,
REV(xya) = REV((xy)a) = a REV(xy).
But by induction hypothesis a REV(xy) = a REV(y)REV(x).
Since a REV(y) = REV(ya), REV(xya) = REV(ya)REV(x), which is what we needed.
End of Proof.