Recursion

Recursive Definition

Sets which have too many elements to list them up, and for which there are no convenient or obvious predicates to specify their elements can often be defined using a recursive definition (also called inductive definition). It essentially gives a procedure to generate the members of the set one by one starting with some subset of its elements. In this type of definition, first a collection of elements to be included initially in the set is specified. These elements can be viewed as the seeds of the set being defined. Next, the rules to be used to generate elements of the set from elements already known to be in the set (initially the seeds) are given. These rules provide a method to construct the set element by element starting with the seeds. These rules can also be used to test elements for the membership in the set.

A recursive definition of a set always consists of three distinct clauses:

1. The basis clause (or simply basis) of the definition establishes that certain objects are in the set. This part of the definition specifies the "seeds" of the set from which the elements of the set are generated using the methods given in the inductive clause. The set of elements specified here is called basis of the set being defined.

2. The inductive clause (or simply induction) of the definition establishes the ways in which elements of the set can be combined to produce new elements of the set. The inductive clause always asserts that if objects are elements of the set, then they can be combined in certain specified ways to create other objects. Let us call the objects used to create a new object the parents of the new object, and the new object is their child.

3. The extremal clause asserts that unless an object can be shown to be a member of the set by applying the basis and inductive clauses a finite number of times, the object is not a member of the set.

The set you are trying to define recursively is the set that satisfies those three clauses.

There are a number of other ways of expressing the extremal clause that are equivalent to the extremal clause given above.

Examples of Recursive Definition of Set

Example 1. Definition of the Set of Natural Numbers N

The set N is the set that satisfies the following three clauses:

Basis Clause: 0 ∈ N

Inductive Clause: For any element x in N, x + 1 is in N.

Extremal Clause: Nothing is in N unless it is obtained from the Basis and Inductive Clauses.

The basis for this set N is { 0 } . The x + 1 in the Inductive Clause is the parent of x, and x is the child of x + 1. Following this definition, the set of natural numbers N can be obtained as follows:

First by the Basis Clause, 0 is put into N. Then by the Inductive Clause, since 0 is in N, 0 + 1 (= 1) is in N. 0 is the parent of 1, and 1 is the child of 0. Then by the Inductive Clause again, 1 + 1 (= 2) is in N. 1 is the parent of 2, and 2 is the child of 1. Proceeding in this manner all the "natural numbers" are put into N.

Note that if we don't have the Extremal Clause, 0.5, 1.5, 2.5, ... can be included in N, which is not what we want as the set of natural numbers.

Example 2. Definition of the Set of Nonnegative Even Numbers NE

The set NE is the set that satisfies the following three clauses:

Basis Clause: 0 ∈ NE

Inductive Clause: For any element x in NE, x + 2 is in NE.

Extremal Clause: Nothing is in NE unless it is obtained from the Basis and Inductive Clauses.

Example 3. Definition of the Set of Even Integers EI

The set EI is the set that satisfies the following three clauses:

Basis Clause: 0 ∈ EI

Inductive Clause: For any element x in EI, x + 2, and x - 2 are in EI.

Extremal Clause: Nothing is in EI unless it is obtained from the Basis and Inductive Clauses.

Example 4. Definition of the Set of Strings S over the alphabet {a,b} excepting empty string. This is the set of strings consisting of a's and b's such as abbab, bbabaa, etc.

The set S is the set that satisfies the following three clauses:

Basis Clause: a ∈ S, and b ∈ S.

Inductive Clause: For any element x in S, ax ∈ S, and bx ∈ S.

Here ax means the concatenation of a with x.

Extremal Clause: Nothing is in S unless it is obtained from the Basis and Inductive Clauses.

Tips for recursively defining a set:

For the "Basis Clause", try simplest elements in the set such as smallest numbers (0, or 1), simplest expressions, or shortest strings. Then see how other elements can be obtained from them, and generalize that generation process for the "Inductive Clause".

The set of propositions (propositional forms) can also be defined recursively.

Generalized Set Operations

As we saw earlier, union, intersection and Cartesian product of sets are associative. For example (A ∪ B) ∪ C = A ∪ (B ∪ C)

To denote either of these we often use A ∪ B ∪ C.

This can be generalized for the union of any finite number of sets as A1 ∪ A2 ∪.... ∪ An.

which we write as

i=1nAi size 12{ union rSub { size 8{i=1} } rSup { size 8{n} } A rSub { size 8{i} } } {}

This generalized union of sets can be rigorously defined as follows:

Definition ( i=1nAi size 12{ union rSub { size 8{i=1} } rSup { size 8{n} } A rSub { size 8{i} } } {}):

Basis Clause: For n = 1, i=1nAi=A1 size 12{ union rSub { size 8{i=1} } rSup { size 8{n} } A rSub { size 8{i} } =A rSub { size 8{1} } } {}.

Inductive Clause: i=1n+1Ai size 12{ union rSub { size 8{i=1} } rSup { size 8{n+1} } A rSub { size 8{i} } } {} = i=1nAi size 12{ union rSub { size 8{i=1} } rSup { size 8{n} } A rSub { size 8{i} } } {}∪ An+1

Similarly the generalized intersection i=1nAi size 12{ intersection rSub { size 8{i=1} } rSup { size 8{n} } A rSub { size 8{i} } } {}and generalized Cartesian product i=1nAi size 12{ times rSub { size 8{i=1} } rSup { size 8{n} } A rSub { size 8{i} } } {} can be defined.

Based on these definitions, De Morgan's law on set union and intersection can also be generalized as follows:

Theorem (Generalized De Morgan)

i=1nAi¯=i=1nAi¯ size 12{ {overline { union rSub { size 8{i=1} } rSup { size 8{n} } A rSub { size 8{i} } }} = intersection rSub { size 8{i=1} } rSup { size 8{n} } {overline {A rSub { size 8{i} } }} } {}, and

i = 1 n A i ¯ = i = 1 n A i ¯ size 12{ {overline { intersection rSub { size 8{i=1} } rSup { size 8{n} } A rSub { size 8{i} } }} = union rSub { size 8{i=1} } rSup { size 8{n} } {overline {A rSub { size 8{i} } }} } {}

Proof: These can be proven by induction on n and are left as an exercise.

Recursive Definition of Function

Some functions can also be defined recursively.

Condition: The domain of the function you wish to define recursively must be a set defined recursively.

How to define function recursively: First the values of the function for the basis elements of the domain are specified. Then the value of the function at an element, say x, of the domain is defined using its value at the parent(s) of the element x.

A few examples are given below.

They are all on functions from integer to integer except the last one.

Example 5: The function f(n) = n! for natural numbers n can be defined recursively as follows:

The function f is the function that satisfies the following two clauses:

Basis Clause: f(0) = 0! = 1

Inductive Clause: For all natural number n, f(n+1) = (n+1) f(n).

Note that here Extremal Clause is not necessary, because the set of natural numbers can be defined recursively and that has the extremal clause in it. So there is no chance of other elements to come into the function being defined.

Using this definition, 3! can be found as follows:

Since 0 ! = 1, 1 ! = 1 * 0 ! = 1 * 1 = 1 ,

Hence 2 ! = 2 * 1 ! = 2 * 1 = 2 .

Hence 3 ! = 3 * 2 ! = 3 * 2 * 1 = 6 .

Example 6: The function f(n) = 2n + 1 for natural numbers n can be defined recursively as follows:

The function f is the function that satisfies the following two clauses:

Basis Clause: f(0) = 1

Inductive Clause: For all natural number n, f(n+1) = f(n) + 2 .

See above for the extremal clause.

Example 7: The function f(n) = 2n for natural numbers n can be defined recursively as follows:

The function f is the function that satisfies the following two clauses:

Basis Clause: f(0) = 1

Inductive Clause: For all natural number n, f(n+1) = 2 f(n) .

See Example 5 for the extremal clause.

Example 8: The function L from the set S of strings over {a, b} to the set of natural numbers that gives the length of a string can be defined recursively as follows:

The function L is the function that satisfies the following two clauses:

Basis Clause: For symbols a and b of the alphabet, L(a) = 1 and L(b) = 1.

Inductive Clause: For any string x and y of S, L(xy) = L(x) + L(y) , where xy is the concatenation of strings x and y.

See Example 5 for the extremal clause.

This function L gives the number of a's and b's.

Mathematical Induction -- First Principle

As we have seen in recursion, the set of natural numbers can be defined recursively, and its elements can be generated one by one starting with 0 by adding 1. Thus the set of natural numbers can be described completely by specifying the basis element (0), and the process of generating an element from a known element in the set.

Taking advantage of this, natural numbers can be proven to have certain properties as follows:

First it is proven that the basis element, that is 0, has the property in question (basis step). You prove that the seeds (the first generation elements) have the property. Then it is proven that if an arbitrary natural number, denote it by n, has the property in question, then the next element, that is n + 1, has that property (inductive step). Here you prove that the property is inherited from one generation (n) to the next generation (n + 1).

When these two are proven, then it follows that all the natural numbers have that property. For since 0 has the property by the basis step, the element next to it, which is 1, has the same property by the inductive step. Then since 1 has the property, the element next to it, which is 2, has the same property again by the inductive step. Proceeding likewise, any natural number can be shown to have the property. This process is somewhat analogous to the knocking over a row of dominos with knocking over the first domino corresponding to the basis step.

More generally mathematical statements involving a natural number n such as 1 + 2 + ... + n = n( n + 1 )/2 can be proven by mathematical induction by the same token.

To prove that a statement P(n) is true for all natural number n≥n0, where n0 is a natural number, we proceed as follows:

Basis Step: Prove that P(n0) is true.

Induction: Prove that for any integer k≥n0, if P(k) is true (called induction hypothesis), then P(k+1) is true.

The first principle of mathematical induction states that if the basis step and the inductive step are proven, then P(n) is true for all natural number n≥n0.

As a first step for proof by induction, it is often a good idea to restate P(k+1) in terms of P(k) so that P(k), which is assumed to be true, can be used.

Example:

Prove that for any natural number n, 0 + 1 + ... + n = n( n + 1 )/2 .

Proof:

Basis Step: If n = 0, then LHS = 0, and RHS = 0 * (0 + 1) = 0 .

Hence LHS = RHS.

Induction: Assume that for an arbitrary natural number n, 0 + 1 + ... + n = n( n + 1 )/2 .

-------- Induction Hypothesis

To prove this for n+1, first try to express LHS for n+1 in terms of LHS for n, and somehow use the induction hypothesis.

Here let us try

LHS for n + 1 = 0 + 1 + ... + n + (n + 1) = (0 + 1 + ... + n) + (n + 1).

Using the induction hypothesis, the last expression can be rewritten as

n( n + 1 )/2 + (n + 1) .

Factoring (n + 1) out, we get

(n + 1)(n + 2) / 2,

which is equal to the RHS for n+1.

Thus LHS = RHS for n+1.

End of Proof.

Example of Use of Mathematical Induction --- Program Correctness

Loops in an algorithm/program can be proven correct using mathematical induction. In general it involves something called "loop invariant" and it is very difficult to prove the correctness of a loop. Here we are going to give a few examples to convey the basic idea of correctness proof of loop algorithms.

First consider the following piece of code that computes the square of a natural number:

(We do not compute the square this way but this is just to illustrate the concept of loop invariant and its proof by induction.)

SQUARE Function: SQ(n)

S <- 0

i <- 0

while i < n

S <- S + n

i <- i + 1

return S

Let us first see how this code computes the square of a natural number. For example let us compute 3 2 using it.

First S <- 0 and i <- 0 give S = 0 and i = 0 initially.

Since i < 3, the while loop is entered.

S <- 0 + 3

i <- 0 + 1

producing S = 3 and i = 1.

Since i < 3, the while loop is entered the second time.

S <- 3 + 3

i <- 1 + 1

producing S = 6 and i = 2.

Since i < 3, the while loop is entered the third time.

S <- 6 + 3

i <- 2 + 1

producing S = 9 and i = 3.

Since i = 3, the while loop is not entered any longer, S = 9 is returned and the algorithm is terminated.

In general to compute n2 by this algorithm, n is added n times.

To prove that the algorithm is correct, let us first note that the algorithm stops after a finite number of steps. For i increases one by one from 0 and n is a natural number. Thus i eventually becomes equal to n.

Next, to prove that it computes n2, we show that after going through the loop k times, S = k*n and i = k hold. This statement is called a loop invariant and mathematical induction can be used to prove it.

Proof by induction.

Basis Step: k = 0. When k = 0, that is when the loop is not entered, S = 0 and i = 0. Hence S = k*n and i = k hold.

Induction Hypothesis: For an arbitrary value m of k, S = m * n and i = m hold after going through the loop m times.

Inductive Step: When the loop is entered (m + 1)-st time, S = m*n and i = m at the beginning of the loop. Inside the loop,

S <- m*n + n

i <- i + 1

producing S = (m + 1)*n and i = m + 1.

Thus S = k*n and i = k hold for any natural number k.

Now, when the algorithm stops, i = n. Hence the loop will have been entered n times.

Thus S = n*n = n2. Hence the algorithm is correct.

The next example is an algorithm to compute the factorial of a positive integer.

FACTORIAL Function: FAC(n)

i <- 1

F <- 1

while i < = n

F <- F * i

i <- i + 1

return F

Let us first see how this code computes the factorial of a positive integer. For example let us compute 3!.

First i <- 1 and F <- 1 give i = 1 and F = 1 initially.

Since i < 3, the while loop is entered.

F <- 1 * 1

i <- 1 + 1

producing F = 1 and i = 2.

Since i < 3, the while loop is entered the second time.

F <- 1 * 2

i <- 2 + 1

producing F = 2 and i = 3.

Since i = 3, the while loop is entered the third time.

F <- 2 * 3

i <- 3 + 1

producing F = 6 and i = 4.

Since i = 4, the while loop is not entered any longer, F = 6 is returned and the algorithm is terminated.

To prove that the algorithm is correct, let us first note that the algorithm stops after a finite number of steps. For i increases one by one from 1 and n is a positive integer. Thus i eventually becomes equal to n.

Next, to prove that it computes n!, we show that after going through the loop k times, F = k ! and i = k + 1 hold. This is a loop invariant and again we are going to use mathematical induction to prove it.

Proof by induction.

Basis Step: k = 1. When k = 1, that is when the loop is entered the first time, F = 1 * 1 = 1 and i = 1 + 1 = 2. Since 1! = 1, F = k! and i = k + 1 hold.

Induction Hypothesis: For an arbitrary value m of k, F = m! and i = m + 1 hold after going through the loop m times.

Inductive Step: When the loop is entered (m + 1)-st time, F = m! and i = (m+1) at the beginning of the loop. Inside the loop,

F <- m!* (m + 1)

i <- (m + 1) + 1

producing F = (m + 1)! and i = (m + 1) + 1.

Thus F = k! and i = k + 1 hold for any positive integer k.

Now, when the algorithm stops, i = n + 1. Hence the loop will have been entered n times. Thus F = n! is returned. Hence the algorithm is correct.

Mathematical Induction -- Second Principle

There is another form of induction over the natural numbers based on the second principle of induction to prove assertions of the form ∀x P(x). This form of induction does not require the basis step, and in the inductive step P(n) is proved assuming P(k) holds for all k < n . Certain problems can be proven more easily by using the second principle than the first principle because P(k) for all k < n can be used rather than just P(n - 1) to prove P(n).

Formally the second principle of induction states that

if ∀n [ ∀k [ k < n → size 12{ rightarrow } {}P(k) ] → size 12{ rightarrow } {}P(n) ] , then ∀n P(n) can be concluded.

Here ∀k [ k < n → size 12{ rightarrow } {}P(k) ] is the induction hypothesis.

The reason that this principle holds is going to be explained later after a few examples of proof. Example 1: Let us prove the following equality using the second principle:

For any natural number n , 1 + 3 + ... + ( 2n + 1 ) = ( n + 1 )2.

Proof: Assume that 1 + 3 + ... + ( 2k + 1 ) = ( k + 1 )2 holds for all k, k < n.

Then 1 + 3 + ... + ( 2n + 1 ) = ( 1 + 3 + ... + ( 2n - 1 ) ) + ( 2n + 1 )

= n2 + ( 2n + 1 ) = ( n + 1 )2 by the induction hypothesis.

Hence by the second principle of induction 1 + 3 + ... + ( 2n + 1 ) = ( n + 1 )2 holds for all natural numbers.

Example 2: Prove that for all positive integer n, ∑i=1n size 12{ Sum rSub { size 8{i=1} } rSup { size 8{n} } {} } {}i ( i! ) = ( n + 1 )! - 1

Proof: Assume that

1 * 1! + 2 * 2! + ... + k * k! = ( k + 1 )! - 1 for all k, k < n.

Then 1 * 1! + 2 * 2! + ... + ( n - 1 ) * ( n - 1 )! + n * n!

= n! - 1 + n * n! by the induction hypothesis.

= ( n + 1 )n! - 1

Hence by the second principle of induction ∑i=1n size 12{ Sum rSub { size 8{i=1} } rSup { size 8{n} } {} } {}i ( i! ) = ( n + 1 )! - 1 holds for all positive integers.

Example 3: Prove that any positive integer n, n > 1, can be written as the product of prime numbers.

Proof: Assume that for all positive integers k, n > k > 1, k can be written as the product of prime numbers.

We are going to prove that n can be written as the product of prime numbers.

Since n is an integer, it is either a prime number or not a prime number. If n is a prime number, then it is the product of 1, which is a prime number, and itself. Therefore the statement holds true.

If n is not a prime number, then it is a product of two positive integers, say p and q. Since both p and q are smaller than n, by the induction hypothesis they can be written as the product of prime numbers (Note that this is not possible, or at least very hard, if the First Principle is being used). Hence n can also be written as the product of prime numbers.