Skip to content

30_Recursive Definitions and Structural Induction

1. Recursively Defined Functions

A recursive (or inductive) definition of a function \(f(n)\) over non-negative integers consists of two steps:

  1. Basis Step: Specify the value of the function at zero (or another initial starting point).

  2. Recursive Step: Provide a rule for finding its value at an integer based on its values at smaller integers.

Note: A function \(f(n)\) defined this way is equivalent to a sequence \(a_0, a_1, \dots\) where \(f(i) = a_i\).

Examples of Recursive Functions:

  • Arbitrary Function: Given \(f(0) = 3\) and \(f(n+1) = 2f(n) + 3\).

    • \(f(1) = 2(3) + 3 = 9\)

    • \(f(2) = 2(9) + 3 = 21\)

  • Factorial (\(n!\)):

    • \(f(0) = 1\)

    • \(f(n+1) = (n+1) \cdot f(n)\)

  • Summation (\(\sum_{k=0}^{n} a_k\)):

    • Basis: \(\sum_{k=0}^{0} a_k = a_0\)

    • Recursive: \(\sum_{k=0}^{n+1} a_k = \left(\sum_{k=0}^{n} a_k\right) + a_{n+1}\)

2. The Fibonacci Sequence

The Fibonacci sequence models natural phenomena (like population growth) and is strictly defined via recursion:

  • \(f_0 = 0\)

  • \(f_1 = 1\)

  • \(f_n = f_{n-1} + f_{n-2}\) (for \(n \geq 2\))

Key Property (Proved via Strong Induction):

For \(n \geq 3\), \(f_n > \alpha^{n-2}\), where \(\alpha = \frac{1 + \sqrt{5}}{2}\) (the Golden Ratio).

  • Proof insight: The proof relies on the algebraic property that \(\alpha^2 = \alpha + 1\). In the inductive step, substituting \(\alpha^{k-1} = \alpha^{k-2} + \alpha^{k-3}\) perfectly matches the recursive sum \(f_{k+1} = f_k + f_{k-1}\).

3. Euclidean Algorithm and Lamé's Theorem

The Euclidean Algorithm efficiently computes the greatest common divisor (gcd) using the principle that \(\gcd(a,b) = \gcd(b, a \bmod b)\).

Lamé's Theorem:

Let \(a\) and \(b\) be positive integers with \(a \geq b\). 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\).

  • Complexity: As a direct consequence of Lamé's Theorem, the time complexity of the Euclidean algorithm is \(O(\log b)\).

4. Recursively Defined Sets and Structures

Sets can be constructed using recursive definitions, which universally assume an exclusion rule: the set contains only the elements specified by the basis step and those generated by the recursive step.

Examples of Recursive Sets:

  • Subset of Integers (Multiples of 3):

    • Basis: \(3 \in S\)

    • Recursive: If \(x \in S\) and \(y \in S\), then \(x + y \in S\).

  • Strings over an Alphabet (\(\Sigma^*\)):

    • Basis: \(\lambda \in \Sigma^*\) (where \(\lambda\) is the empty string).

    • Recursive: If \(w \in \Sigma^*\) and \(x \in \Sigma\), then \(wx \in \Sigma^*\).

  • Well-Formed Formulae in Propositional Logic:

    • Basis: \(\mathbf{T}, \mathbf{F}\), and propositional variables (\(s\)) are well-formed.

    • Recursive: If \(E\) and \(F\) are well-formed, then \((\neg E), (E \land F), (E \lor F), (E \rightarrow F), (E \leftrightarrow F)\) are well-formed.

Recursive Operations on Strings:

  • Concatenation (\(w_1 \cdot w_2\)): Basis: \(w \cdot \lambda = w\). Recursive: \(w_1 \cdot (w_2x) = (w_1 \cdot w_2)x\).

  • Length (\(l(w)\)): Basis: \(l(\lambda) = 0\). Recursive: \(l(wx) = l(w) + 1\).

5. Rooted and Full Binary Trees

Rooted Trees:

  • Basis: A single vertex \(r\) is a rooted tree.

  • Recursive: Suppose \(T_1, T_2, \dots, T_n\) are disjoint rooted trees with roots \(r_1, r_2, \dots, r_n\). A new graph formed by taking a root \(r\) and adding edges to \(r_1, r_2, \dots, r_n\) is also a rooted tree.

Full Binary Trees:

  • Basis: A single vertex \(r\) is a full binary tree.

  • Recursive: If \(T_1\) and \(T_2\) are disjoint full binary trees, a new full binary tree \(T_1 \cdot T_2\) is formed by connecting a root \(r\) to the roots of \(T_1\) and \(T_2\).

  • Height \(h(T)\): Basis: \(h(T) = 0\). Recursive: \(h(T) = 1 + \max(h(T_1), h(T_2))\).

  • Vertices \(n(T)\): Basis: \(n(T) = 1\). Recursive: \(n(T) = 1 + n(T_1) + n(T_2)\).

6. Structural Induction

Structural induction is a proof technique used specifically for demonstrating that a property holds for all elements of a recursively defined set. Its validity stems from standard mathematical induction.

Steps for Structural Induction:

  1. Basis Step: Show that the property holds for all elements specified in the basis step of the set's recursive definition.

  2. Recursive Step: Show that if the property is true for the foundational elements used to construct new elements, it must also hold for the newly constructed elements.

Example Theorem: If \(T\) is a full binary tree, then its number of vertices satisfies \(n(T) \leq 2^{h(T)+1} - 1\).

  • Proof by Structural Induction:

    • Basis: For a single vertex tree, \(n(T) = 1\) and \(h(T) = 0\). \(1 \leq 2^{0+1} - 1 = 1\). (True)

    • Recursive: Assume \(n(T_1) \leq 2^{h(T_1)+1} - 1\) and \(n(T_2) \leq 2^{h(T_2)+1} - 1\).

      \(n(T) = 1 + n(T_1) + n(T_2) \leq 1 + (2^{h(T_1)+1} - 1) + (2^{h(T_2)+1} - 1) \leq 2 \cdot \max(2^{h(T_1)+1}, 2^{h(T_2)+1}) - 1 = 2 \cdot 2^{h(T)} - 1 = 2^{h(T)+1} - 1\).

7. Generalized Induction

Generalized induction extends induction to sets beyond integers that possess a well-ordering property (e.g., \(\mathbb{N} \times \mathbb{N}\) pairs or strings ordered lexicographically).

  • Lexicographic Ordering: \((x_1, y_1)\) is less than or equal to \((x_2, y_2)\) if \(x_1 < x_2\), or if \(x_1 = x_2\) and \(y_1 \leq y_2\).

8. Fractals (Visual Recursion)

Fractals are geometric shapes constructed using recursive patterns that repeat indefinitely across different scales and orientations.

  • Koch Curve: A curve where order \(n\) consists of four copies of order \(n-1\).

  • Koch Snowflake: Constructed from three Koch curves.

  • Sierpinski Triangle: Formed by a confined recursion of extracting smaller triangles to create a geometric lattice.