Induction
Basis Step: Prove that P(x) is true for all the elements x in the basis of S.
Induction Step: 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.
Note 1 :
In the Basis Step we prove that the seeds have the property.
In the Induction Step we prove that the property is inherited from generation to generation, that is, we prove that if a parent has the property
then all of its children
also have that property. In the process we need the relationship between the parent and the children.
That relationship is found in the Inductive Clause of the recursive definition of the set in question.
Note 2: As the result of the Basis Step, we know that the seeds have the property in question. Then by the Induction Step we can say that the members of the second generation (children of the seeds) have the property. Then again by the Induction Step we can say that the members of the third generation(children of the second generation) have the property.....Thus we can say that all the members of the set have the property.
Note 3 : As a first step for general induction proof, it is often a good idea to express y
in terms of x
so that P(x) can be used.
Example 1 (Theorem 1 in "Language") : Prove that Ln
L*
for any natural number n and any language L.
Let us first review the definitions.
Recursive definition of Lk:
Basis Clause: L0 =
{}
Inductive Clause: L(k+1) = LkL.
Since Lk is defined for natural numbers k, the extremal clause is not necessary.
Recursive definition of L*:
Basis Clause:
L*
Inductive Clause: For any string x
L* and any string w L,
xw L*.
Extremal Clause: Nothing is in L* unless it is obtained from the above
two clauses.
Now let us prove that Ln
L* by induction on Ln.
Note in the proof below that Basis and Induction Steps mirror the Basis and Inductive Clauses
of the definition of Ln .
Basis Step: Since by the definitions
L0 = {}, and
L* , L0
L* .
Induction Step: Assume that Lk
L* for an arbitrary natural numer k.
--- Induction Hypothesis
We are going to show that Lk+1
L* .
Let w be an arbitrary string in Lk+1 . Then there exist strings x and y
that satisfy x Lk ,
y L and w = xy by the definition of Lk+1.
Since Lk
L* by theInduction Hypothesis,
x L* .
Then by the definition of L*,
xy L*
since y L .
Hence w L* .
Thus Lk+1
L* .
Example 2 (Theorem 2 in "Language") Let us prove
L* = .
Note that =
{ x | x Lk
for some natural number k } .
Proof: Let us first prove
L* .
Suppose that x
. Then by the definition of
,
x Lk for some natural number k.
By Example 1 above , Lk
L* . Hence x L* .
Hence
L* .
Next let us prove L*
.
Note that L* is
Basis Step:
L0 since
L0 =
{} .
Hence by the definition of ,
.
Induction Step: Assume that for an arbitrary x in L*,
x
holds.
We are going to show that for an arbitrary element y
L ,
xy
holds.
Note here that x is a parent and by applying an operation (i.e. by concatenating y) a child of x
in is obtained.
So we show that the property for x is inherited by its children xy. Let us prove the inheritance.
If x
, then for some
natural number k , x Lk .
Hence xy Lk+1 by the definition
of Ln . Hence
xy
by Example 1 above.
End of Induction Step and Proof
Hence we have proven .
Example 3
Prove that for arbitrary strings x and y of ,
REV(xy) = REV(y) REV(x) holds.
The function REV(x) on strings
x
over the alphabet
is defined as follows. It produces
the reversal of a given string x (i.e. x spelled backward).
Basis Clause: REV() = .
Inductive Clause: For any string and any symbol , REV(xa) = aREV(x).
Note that each step mirror the recursive definition of
.
Proof
First let us note that
*
can be defined recursively as follows:
Basis Clause:
*
where
is an empty string.
Inductive Clause: 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 Step:
REV(x) = REV( x ) = REV()REV( x ) .
Induction Step: 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.