5.3 Recursive Definitions & Structural Induction

A recursive definition has two parts: a basis step (starting values or elements) and a recursive step (how to build new ones from old ones). Structural induction is how you prove things about objects defined this way.

Recursively defined functions

Recursive function on

N

Basis step: give $f (0)$ (or the first few values).
Recursive step: give a rule for $f (n + 1)$ in terms of earlier values.

From class:

a_{n} = 4^{n}

for

n \geq 0

, expressed recursively

Basis: $a_{0} = 4^{0} = 1$ . Recursive rule: $a_{n} = 4 a_{n - 1}$ for $n \geq 1$ .

Explicit formula → recursive definition

Ask: how do I get $a_{n + 1}$ from $a_{n}$ ?

Explicit	Recursive step	Basis
$a_{n} = c + d n$ (arithmetic)	$a_{n + 1} = a_{n} + d$	$a_{0} = c$
$a_{n} = c \cdot r^{n}$ (geometric)	$a_{n + 1} = r \cdot a_{n}$	$a_{0} = c$
$S_{n} = \sum_{i = 0}^{n} b_{i}$	$S_{n + 1} = S_{n} + b_{n + 1}$	$S_{0} = b_{0}$
$n!$	$(n + 1)! = (n + 1) \cdot n!$	$0! = 1$
$P_{m} (n) = mn$	$P_{m} (n + 1) = P_{m} (n) + m$	$P_{m} (0) = 0$

Always state the basis. A recursive rule without a starting value defines nothing.

Computing values

Make a table and fill it in order: $f (0), f (1), f (2), \dots$ Each value only uses ones you have already written down. With two previous terms (like Fibonacci) you need two starting values.

Fibonacci numbers

$f_{0} = 0$ , $f_{1} = 1$ , and $f_{n} = f_{n - 1} + f_{n - 2}$ for $n \geq 2$ .

$n$	0	1	2	3	4	5	6	7	8
$f_{n}$	0	1	1	2	3	5	8	13	21

Recursively defined sets

Recursive set

Basis step: list the initial elements.
Recursive step: rules that build new elements from elements already in the set.
Exclusion rule (implicit): nothing else is in the set.

From class:

5 \in S

; if

x, y \in S

then

x + y \in S

Generate: $5$ , then $10$ , then $15, 20$ , … so $S = {5 n ∣ n \in Z^{+}}$ , the positive multiples of 5. (Proving this takes two inclusions. See Structural induction below.)

Writing a recursive definition for a set of integers

Find the period of the pattern. The basis lists one "block" of elements; the recursive step adds the period.

Set	Basis	Recursive step
Positive multiples of 5	$5 \in S$	$x \in S \Rightarrow x + 5 \in S$
Odd positive integers	$1 \in S$	$x \in S \Rightarrow x + 2 \in S$
${n \in Z^{+} : n \equiv 3 (mod 4)}$	$3 \in S$	$x \in S \Rightarrow x + 4 \in S$
Positive integers not divisible by 7	$1, 2, 3, 4, 5, 6 \in S$	$x \in S \Rightarrow x + 7 \in S$
All even integers (incl. negatives)	$0 \in S$	$x \in S \Rightarrow x + 2, x - 2 \in S$
Positive powers of 3	$3 \in S$	$x \in S \Rightarrow 3 x \in S$
$Z^{+}$	$1 \in S$	$x, y \in S \Rightarrow x + y \in S$

If the set includes negative numbers, you need a rule that goes down too.

Strings

Strings over an alphabet

Σ

$λ$ is the empty string (no characters).
$Σ^{*}$ (the Kleene closure) is the set of all strings over $Σ$ , defined recursively: $λ \in Σ^{*}$ ; if $w \in Σ^{*}$ and $x \in Σ$ then $w x \in Σ^{*}$ .
Concatenation $w x$ is " $w$ followed by $x$ ." It is not commutative: $001 \cdot 1101 = 0011101$ but $1101 \cdot 001 = 1101001$ . For every string, $λ w = w λ = w$ .

Convention: $a, b, c \in Σ$ are symbols; $w, x, y, z \in Σ^{*}$ are strings.

Recursive functions on strings (the pattern: say what

λ

gives, then what adding one symbol does)

Function	Basis	Recursive step ( $w \in Σ^{*}$ , $a \in Σ$ )
length $l (w)$	$l (λ) = 0$	$l (w a) = l (w) + 1$
number of 1s, bit strings	$ones (λ) = 0$	$ones (w b) = ones (w) + b$ , for $b \in {0, 1}$
number of 0s, bit strings	$z (λ) = 0$	$z (w b) = z (w) + (1 - b)$
reversal $w^{R}$	$λ^{R} = λ$	$(w a)^{R} = a w^{R}$
power $w^{i}$	$w^{0} = λ$	$w^{i + 1} = w w^{i}$

Recursive sets of strings

Set	Basis	Recursive step
Palindromes (bit strings)	$λ, 0, 1 \in P$	$w \in P \Rightarrow 0 w 0, 1 w 1 \in P$
${0^{n} 1^{n} : n \geq 0}$	$λ \in A$	$x \in A \Rightarrow 0 x 1 \in A$

Well-formed formulae

Formulas are defined recursively too: the basis gives the atoms, the recursive step gives the operators with parentheses.

Propositional logic: Basis: $T$ , $F$ , and every propositional variable. Recursive: if $E, F$ are wffs, so are $(\neg E)$ , $(E \land F)$ , $(E \lor F)$ , $(E \to F)$ , $(E \leftrightarrow F)$ .
Arithmetic: Basis: every numeral and variable. Recursive: $(F + G)$ , $(F - G)$ , $(F * G)$ , $(F / G)$ , $(F ↑ G)$ .
Sets: Basis: every set or set variable. Recursive: $X$ , $(X \cup Y)$ , $(X \cap Y)$ , $(X - Y)$ .

Full binary trees

Full binary tree

Basis: a single vertex $r$ is a full binary tree.
Recursive: if $T_{1}, T_{2}$ are disjoint full binary trees, then $T = T_{1} \cdot T_{2}$ (a new root $r$ with left subtree $T_{1}$ and right subtree $T_{2}$ ) is a full binary tree.

Tree functions to memorize

	Basis (single root)	Recursive ( $T = T_{1} \cdot T_{2}$ )
height $h (T)$	$0$	$1 + max (h (T_{1}), h (T_{2}))$
vertices $n (T)$	$1$	$1 + n (T_{1}) + n (T_{2})$
leaves $l (T)$	$1$	$l (T_{1}) + l (T_{2})$
internal vertices $i (T)$	$0$	$1 + i (T_{1}) + i (T_{2})$

Facts (all proved by structural induction): $n (T) \leq 2^{h (T) + 1} - 1$ , $n (T) \geq 2 h (T) + 1$ , $l (T) = i (T) + 1$ .

Structural induction

To prove a property holds for every element of a recursively defined set:

Basis step: show it holds for every element given in the basis.
Recursive step: assume it holds for the elements $x_{1}, \dots, x_{k}$ used in a recursive rule (this is the IH). Show it holds for the new element built from them. Do this for every recursive rule.

Structural induction templates

Integers / sets: Basis: check the listed elements. Step: "Assume $x$ (and $y$ ) have the property; show $x + y$ (or $3 x$ , $x^{2}$ , …) does too."

Strings: Basis: prove $P (λ)$ . Step: assume $P (w)$ , prove $P (w a)$ for every $a \in Σ$ .

Full binary trees: Basis: prove it for the single-vertex tree. Step: assume it for $T_{1}$ and $T_{2}$ , prove it for $T_{1} \cdot T_{2}$ using the recursive formulas for $h$ , $n$ , $l$ , $i$ .

Proving a recursive set equals a described set

To show $S = A$ , prove both inclusions.

From class:

4 \in S

; if

x, y \in S

then

x + y \in S

. Prove

S = A = {4 n ∣ n \in Z^{+}}

Proof

Part 1: $A \subseteq S$ (ordinary induction on $n$ ). Let $P (n)$ : $4 n \in S$ .

Basis: $4 \cdot 1 = 4 \in S$ by the basis step.
Step: if $4 n \in S$ , then since $4 \in S$ too, the recursive step gives $4 n + 4 = 4 (n + 1) \in S$ .

Part 2: $S \subseteq A$ (structural induction).

Basis: $4 = 4 \cdot 1 \in A$ .
Step: assume $x, y \in S$ are in $A$ , so $4 ∣ x$ and $4 ∣ y$ . Then $4 ∣ (x + y)$ and $x + y > 0$ , so $x + y \in A$ .

By Parts 1 and 2, $S = A$ . ∎

From class (textbook Example 12):

l (x y) = l (x) + l (y)

for all strings

x, y

Proof

Fix $x$ and use structural induction on $y$ . Let $P (y)$ : $l (x y) = l (x) + l (y)$ .

Basis ( $y = λ$ ): $l (x λ) = l (x) = l (x) + 0 = l (x) + l (λ)$ .

Recursive step. Assume $P (y)$ . For any $a \in Σ$ :
$l (x (y a)) = l ((x y) a) = l (x y) + 1 = l (x) + l (y) + 1 = l (x) + l (y a) definition of l IH definition of l .$ ∎

Every element of

S

has property

Q

(the "mod" pattern, 5.3 #26/#27 style)

$S$ : $5 \in S$ ; if $n \in S$ then $3 n \in S$ and $n^{2} \in S$ . Show every $n \in S$ satisfies $n \equiv 5 (mod 10)$ .

Proof

Basis: $5 \equiv 5 (mod 10)$ .
Recursive step: Assume $n \equiv 5 (mod 10)$ . Then $3 n \equiv 15 \equiv 5$ and $n^{2} \equiv 25 \equiv 5 (mod 10)$ . Both new elements have the property. ∎

Showing the converse fails: $35 \equiv 5 (mod 10)$ , but $35 \neq = 5$ , $35$ is not $3 n$ for an integer $n$ , and $35$ is not a perfect square. So $35 \in / S$ .

Common mistakes

Only checking one of the recursive rules. Every rule needs its own case.
In the basis for strings, the case is $y = λ$ , the empty string.
Using structural induction for the " $A \subseteq S$ " direction. That direction is usually ordinary induction (show each element of $A$ can be built).

Ackermann's function (this book's version)

Definition. Memorize the four cases exactly.

A (m, n) = ⎩ ⎨ ⎧ 2 n 02 A (m - 1, A (m, n - 1)) if m = 0 if m \geq 1, n = 0 if m \geq 1, n = 1 if m \geq 1, n \geq 2

Useful facts: $A (1, n) = 2^{n}$ for $n \geq 1$ , $A (m, 2) = 4$ for $m \geq 1$ , and $A (2, n) = 2^{2^{\cdot^{\cdot^{2}}}}$ (a tower of $n$ twos).

Evaluating Ackermann

Always expand the inner argument first. Example: $A (2, 2) = A (1, A (2, 1)) = A (1, 2) = A (0, A (1, 1)) = A (0, 2) = 4$ .

Fixes to your class notes

"Clean closure" should be Kleene closure ( $A^{*}$ ).
The identity for the empty string is $λ w = w λ = w$ . Your notes wrote $x w = w x = w$ .
In the proof of $l (x y) = l (x) + l (y)$ , the basis case is $y = λ$ , not $y = 2$ .

Exam checklist

Compute values of a recursively defined function (including two-term recurrences and Ackermann).
Convert an explicit formula or a described set into a recursive definition.
Describe the set produced by a recursive definition.
Give recursive definitions on strings (length, ones, reversal, powers, palindromes).
Write a structural induction proof (sets, strings, full binary trees), handling every rule.
Prove $S = A$ via two inclusions.