Induction

General Induction

(a.k.a Structural Induction)

Mathematical statements involving an element of a recursively defined set can be proven by general induction.
To prove by general induction 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 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 Lⁿ L^* for any natural number n and any language L.
Let us first review the definitions.
Recursive definition of L^k:
Basis Clause: L⁰ = {}
Inductive Clause: L^(k+1) = L^kL.
Since L^k 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 Lⁿ L^* by induction on Lⁿ.
Note in the proof below that Basis and Induction Steps mirror the Basis and Inductive Clauses of the definition of Lⁿ .

Basis Step: Since by the definitions L⁰ = {}, and L^* , L⁰ L^* .
Induction Step: Assume that L^k L^* for an arbitrary natural numer k. --- Induction Hypothesis
We are going to show that L^k+1 L^* .
Let w be an arbitrary string in L^k+1 . Then there exist strings x and y that satisfy x L^k , y L and w = xy by the definition of L^k+1. Since L^k L^* by theInduction Hypothesis, x L^* .
Then by the definition of L^*, xy L^* since y L .
Hence w L^* .
Thus L^k+1 L^* .


Example 2 (Theorem 2 in "Language") Let us prove L^* = .
Note that = { x | x L^k for some natural number k } .
Proof: Let us first prove L^* .
Suppose that x . Then by the definition of ,   x L^k for some natural number k. By Example 1 above , L^k L^* . Hence x L^* . Hence L^* .

Next let us prove L^* .

Note that L^* is defined recursively and that below we are trying to prove that the elements of L^* have the property that they also belong to . So we first prove that the element of the basis of L^* has the propertyy. Then we show that if any element, say x, of L^* has the property, then its children xy, where y is an arbitrary elememt of L, also have the property.

Basis Step: L⁰ since L⁰ = {} .
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 L^k .
Hence xy L^k+1 by the definition of Lⁿ . 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.

More Examples

Test Your Understanding of General Induction

Indicate which of the following statements are correct and which are not.
Click Yes or No , then Submit.
There are two sets of questions.

In the questions below the following notations are used:

L^* and L^+   for   L^* and L⁺ , respectively




Next -- Definitions of Regular Language and Regular Expression

Back to Study Schedule

Back to Table of Contents