STEP-BY-STEP LESSON · §5.9
General Recursive Definitions and Structural Induction
Prove a property of a recursively built object using its construction rules.
Before you begin
Strong Mathematical Induction and the Well-Ordering Principle for the Integers
For our example, P(n) says that integer n≥2 has a prime factorization. To prove P(k+1), assume P(j) for every integer j from 2 through k. Strong induction permits all these earlier cases, not just P(k).
P(2),P(3),…,P(k) ⇒ P(k+1)
Defining Sequences Recursively
A recurrence relates terms but does not by itself specify where to start.
a_0=2
The rule a_n=2a_(n−1)+1 means: take the previous value, double it, and add 1.
a_n=2a_(n−1)+1, n≥1
Symbols
- ε
- empty string
- |w|
- length of string w
- z(w),o(w)
- numbers of zeros and ones in binary string w
Definitions and notation for this topic
Structural induction
For recursively generated objects, prove the property for each base object and show that every permitted construction preserves it.
Here z and o are declared counts of zeros and ones, not global operators. The recursive definition must generate every object under discussion.
Separate glossary example
For binary strings, z(w)+o(w)=|w|. It holds for ε; appending 0 or 1 increases the length and the corresponding symbol count by one.
Alphabet, empty word and length
Σ; ε; |w|
An alphabet Σ is a finite set of permitted symbols. A word or string is a finite sequence of them. ε is the empty word and |w| is the number of symbols in w.
Σ names a set here, whereas ∑ denotes summation. The bars in |w| denote string length, not absolute value or divisibility. A word’s order matters.
Separate glossary example
Over Σ={0,1}, |010|=3 and |ε|=0. The language {ε} contains one word; the empty language ∅ contains none.
Concatenation and Kleene star
uv; KL; L*
uv appends word v after u. For languages K,L, KL={uv:u∈K,v∈L}. L* contains concatenations of any finite number of words from L, including zero words.
Zero concatenated words give ε, so ε belongs to every L*, even ∅*={ε}. The star applies to the preceding language or grouped regular expression; concatenation need not commute.
Separate glossary example
If K={a,b} and L={01}, then KL={a01,b01}. If L={01}, then L*={ε,01,0101,…}.
Step by step
Step 1 / 6
Specify the basic objects
For binary strings, start with the empty string ε, which contains no symbols.
|ε|=0
Without a base, recursive construction has no starting point.
Worked example
Prove that zero count plus one count equals the length of a binary string.
- For ε all counts are 0, so the property holds.
- Assume z(w)+o(w)=|w|. Appending 0 increases the left side by 1 through z, and length also increases by 1.
- Appending 1 increases o instead. Both rules preserve the property, so it holds for all generated strings.
Optional self-check
How many construction cases must be checked when a, b, or c may be appended?
Show answer
Three, plus the base object.