5. Induction and Recursion

5.1 Mathematical Induction (MI)

Mathematical induction is used to prove propositions of the form ∀nP(n), where the universe of discourse is the set of positive integers.

5.1.1 The First Principle of Mathematical Induction

Written in logical expressions:
{P(1) ∧ ∀k [P(k) → P(k+1)]} → ∀n P(n), where the domain is the set of positive integers.
The principle has the following form:

The procedure:

1. Inductive base: Establish P(1)
2. Inductive step: Prove that P(k) → P(k+1) for k≥1
3. Conclusion: The inductive base and the inductive step together imply P(n) ∀ n ≥ 1.

The first principle of MI has a more general form:
∀n[n ≥ k → P(n)]

1. Inductive base: Establish P(k)
2. Inductive step: Prove that P(n) → P(n+1) for n ≥ k

3. Conclusion: The inductive base and the inductive step together imply P(n) ∀ n ≥ k.

   5.1.2 The Second Principle of Mathematical Induction

   Also called Strong Induction, Complete Induction.
   {P(n0)∧∀k [k≥n0∧P(n0)∧P(n0+1)∧…∧P(k) → P(k+1)]}→ ∀n P(n)
   The procedure :

4. Inductive base: Establish P(n0)

5. Inductive step: Prove P(n0)∧P(n0+1)∧…∧P(k) → P(k+1)

6. Conclusion: The inductive base and the inductive step allow one to conclude that P(n) ∀n≥n0

   5.1.3 Well-Ordering Property

   If every nonempty subset of a set has a least element, then we say the set is **well-ordered**. The set of all nonnegative integers and the set of all natural number are well-ordered.
   📋The validity of MI is based on well-ordering property.
   Proof:
   Assume that there is at least one positive integer for which P(n) is false.
   S: the set of positive integer for which P(n) is false.
   Then S is nonempty. By the well-ordering property, S has a least element, which will be denoted by m. Then according to the inductive base, m≠1, m-1 is a positive integer. m-1 is not in S. So P(m-1) is true. Since the implication P(k)→ P(k +1) is also true, P(m) must be true.
   💡The Good and Bad of Mathematical Induction
   • Can be used to prove a conjecture once it has been made and is true.
   • Proofs do not provide insights as to why theorems are true. You can prove a theorem by MI even if you do not have the slightest idea why it is true!
   • Cannot be used to find new theorems.
   🧷Note:

7. The validity of both mathematical induction and strong induction follow from the well-ordering property.

8. In fact, mathematical induction, strong induction, and well-ordering are all equivalent principles!

   5.2 Recursive Definition and Structural Induction

   5.2.1 Recursive Definition

   Recursion is a principle closely related to mathematical induction. In a **recursive definition**, an object is defined in terms of itself. We can recursively define sequences, functions and sets.
   **Recursively defined functions**, with the set of nonnegative integers as its domain:

• Basis Step: Specify the value of the function at 0.
• Recursive Step: Give the rules for finding its value at an integer from its value at smaller integers.

📋Recursively defined functions are well-defined.
Proof:
Let P(n) be the statement “f is well-defined at n“.
P(0) is true.
Assume that P(n-1) is true. Then f is well-defined at n, since f(n) is given in terms of some f(n-1).
Euclidean algorithm is recursive, so its complexity is a little hard to describe. The following theorem is a nice solution to this problem and an elegant application of recursively defined functions.
📋Lamé’s Theorem 拉梅定理
Let a, b be positive integers with a≥b. Then the number of divisions used by the Euclidean algorithm to find gcd(a, b) is less than or equal to five times the number of decimal digits in b.
Proof:
The Euclidean algorithm is represented as the following equations.

Let the number of decimal digits in b be k, then we need to prove n≤5k.
In the eqations above, q1, q2, … , qn-1 ≥ 1, qn ≥ 2, rn < r__n-1
This implies a Fibonacci sequence.


In Fibonacci sequence, let α = (1+√5)/2, then fn>α__n-2 whenever n ≥ 3. So b > αn-1.
So k = lg b > (n-1) lg α > (n-1) / 5. So n≤5k.
**Recursively defined sets**

• Basis Step: Specify an initial collection of elements.
• Recursive Step: Give the rules for constructing elements of the set from other elements already in the set.
• Sometimes the recursive definition has an **exclusion rule**, which specifies that the set contains nothing other than those elements specified in the basis step and generated by applications of the rules in the recursive step. We will always assume that the exclusion rule holds, even if it is not explicitly mentioned.

**String**, the set Σ* of strings over the alphabet Σ

• Basis Step: λ ∈ Σ* (λ is the empty string)
• Recursive Step: If w is in Σ* and x is in Σ, then wx ∈ Σ*.

Here “wx“ is **string concatenation**. Let Σ be a set of symbols and Σ* be the set of strings formed from the symbols in Σ. We can define the concatenation of two strings, denoted by “∙”, recursively as follows. (Often w1 ∙ w2 is written as w1 w2.)

• Basis Step: If w ∈ Σ*, then w ∙ λ= w.
• Recursive Step: If w1 ∈ Σ* and w2 ∈ Σ* and x ∈ Σ, then w1 ∙ (w2 · x)= (w1 ∙ w2) · x.

🌰e.g.
Another important use of recursive definitions to define well-formed formulae of various type.

🌰e.g.
The set of rooted trees, extended binary trees and full binary trees can be defined recursively.
Building up **rooted trees**:

• Basis Step: A single vertex r is a rooted tree.
• Recursive Step: Suppose that T1, T2, … ,T__n are disjoint rooted trees with roots r1, r2,…,r__n, respectively. Then the graph formed by starting with a root r, which is not in any of the rooted trees T1, T2, … ,T__n, and adding an edge from r to each of the vertices r1, r2,…,r__n, is also a rooted tree.

Building up **full binary trees**:

• Basis Step: There is a full binary tree consisting of only a single vertex r.
• Recursive Step: If T__1 and T__2 are disjoint full binary trees, there is a full binary tree, denoted by T1∙T__2, consisting of a root r together with edges connecting the root to each of the roots of the left subtree T__1 and the right subtree T__2.

5.2.2 Structual Induction

A proof by structural induction:

• Basis Step: Show that the result holds for all elements specified in the basis step of the recursive definition to be in the set.
• Recursive Step: Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements.

The validity of structural induction follows from the principle of mathematical induction for the nonnegative integers.

• p(n): the result is true for all elements of the set that are generated by n or fewer applications of the rules in the recursive step of a recursive definition.
• Basis Step: Show that p(0) is true.
• Recursive Step: if we assume p(k) is true, it follows that p(k+1) is true.

🌰e.g.
Show that every well-formed formula for compound propositions contains an equal number of left and right parentheses.
Proof:

• Basis Step: Show that the result is true for T, F, and p, whenever p is a propositional variable.
• Recursive Step: Show that if the result is true for the compound propositions p and q , it is also true for (¬p), (p ∨ q), (p ∧ q), (p→q), (p↔q), and they all contain equal numbers of left and right parentheses.

🌰e.g. Structural Induction and Binary Trees
The **height** h(T) of a full binary tree T is defined recursively as follows:

• Basis Step: The height of a full binary tree T consisting of only a root r is h(T) = 0.
• Recursive Step: If T__1 and T__2 are full binary trees, then the full binary tree T = T1·T__2 has height h(T) = 1 + max(h(T1), h(T2))

The number of **vertices** n(T) of a full binary tree T satisfies the following recursive formula:

• Basis Step: The number of vertices of a full binary tree T consisting of only a root r is n(T) = 1.
• Recursive Step: If T__1 and T__2 are full binary trees, then the full binary tree T = T1·T__2 has the number of vertices n(T) = 1 + n(T1) + n(T2).

📋If T is a full binary tree, then n(T) ≤ 2h(T)+1 - 1.
Proof: Use structural induction.

5.2.3 Generalized Induction

**Generalized induction** is used to prove results about sets other than the integers that have the well-ordering property. For example, consider an ordering on ℕ × ℕ, ordered pairs of nonnegative integers. Specify that (x1, y1) is less than or equal to (x2, y2) if either x1 < x__2, or x1 = x__2 and y1 <y__2. This is called the **lexicographic ordering**. Strings are also commonly ordered by a lexicographic ordering.
🌰e.g.

5.2.4 Recursive Algorithms

An algorithm is called recursive if it solves a problem by reducing it to an instance of the same problem with smaller input. For the algorithm to terminate, the instance of the problem must eventually be reduced to some initial case for which the solution is known.
**Recursion** Successively reducing the computation to the evaluation of the function an smaller integer.
**Iteration** Start with the value of the function at one or more integers, the base cases, and successively apply the recursive definition to find the value of the function at successive large integers.
🧷For every recursive algorithm, there is an equivalent iterative algorithm. Recursive algorithms are often shorter, more elegant, and easier to understand than their iterative counterparts. However, iterative algorithms are usually more efficient in their use of space and time.