Induction

General Induction



Mathematical statements involving an element of a recursively defined set can be proven by induction.
To prove that a statement P(x) is true for all the elements x of a recursively defined set S, proceed as follows:

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 tex2html_wrap_inline75 REV(xy) = REV(y) REV(x) holds.
To see the recursive definition of REV click here.

Proof

First let us note that tex2html_wrap_inline75 can be defined recursively as follows:
Basis: tex2html_wrap_inline81 , where tex2html_wrap_inline83 is an empty string.
Induction: For arbitrary strings x of tex2html_wrap_inline75 and a of tex2html_wrap_inline91 , xa is also in tex2html_wrap_inline75 .
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 tex2html_wrap_inline75 , REV(xy) = REV(y) REV(x) holds. The proof mirrors the recursive definition of tex2html_wrap_inline75 .

Basis: tex2html_wrap_inline111 .
Induction: Assume that for an arbitrary string y of tex2html_wrap_inline75, REV(xy) = REV(y) REV(x) holds. -- Induction Hypothesis
Then for an arbitrary symbol a of tex2html_wrap_inline91 , 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.

More Examples