CMPS 2120 Lecture Notes - Recursive Definitions & Structural Induction
resources:
RECURSIVE DEFINITIONS. (similar to recursive definitions for sequences)
1. basis B: f(0)
2. a rule R: how to obtain f(n) from f(n-1).
EXAMPLE 1.
n!
basis: 0! = 1
rule: n! = n * (n-1)!, n > 0.
EXAMPLE 2.
Towers of Hanoi
How many moves for disks from tower 1 to tower 3 using tower 2 as temp?
T(1) = 1.
T(n) = 2 * T(n-1) + 1, n > 1.
EXAMPLE 3.
Fibonacci seq 1,1,2,3,5,8,13,...
f_0 = 1
f_1 = 1
f_n = f_n-1 + f_n-2, n >=2.
EXAMPLE 4. (recursive definition of sets)
Basis: 7,10 IN S
Recursive rule: if r IN S then r + 7, r + 10 IN S
Start constructing S:
{ 7,10 }
{ 7, 10, 14, 17, 20 }
{ 7, 10, 14, 17, 20, 21, 24, 27, 30 }
etc.
EXAMPLE 5.
Let S be the subset of the set of ordered pairs of integers defined
recursively by
Basis: (0,0) in S.
Recursive rule: If (a, b) IN S then (a+2,b+3) IN S and (a+3, b+2) IN S.
a) List the elements of S produced by the first two applications of the
recursive definition.
S = {(0,0)}
1st: { ... (2,3),(3,2) }
2nd: { . . . . . . . . , (4,6),(5,5),(6,4) }
Sets of this form are *recursively enumerable*, meaning that all elements
in the set can be enumerated by elements that are already in the set and
no elements in the set will be left out.
You can use structural induction on any enumerable sets.
EXAMPLE.
Show that you can speak the English words from 'one' to 'nine hundred ninety
nine' without ever using the letter 'a'.
Start with the set S recursively enumerated as follows:
S = {'one','two','twen','three','thir','four','for','five','fiv','six',
'seven', 'eight','nine','ten','eleven','twelve'}
Rule 1. Add to S, s+'teen' and s+'ty'.
Rule 2. Add to S, s+' hundred '+ one or more words in S from Rule 1.
The set of all English words from numbers from 1 to 999 is a subset of S.
Structural induction:
The letter 'a' is not in the original S. The letter 'a' is not in the strings
in Rule 1 or in Rule 2. Thus the letter 'a' is not in any strings in S that
are constructed from Rule 1 and Rule 2. Since the English words 'one' to
'nine hundred ninety nine' are in a subset of S, it cannot contain the letter
'a'.
STRUCTURAL INDUCTION ON RECURSIVELY ENUMERABLE SETS.
1. Basis: Establish the property for each atomic element.
2. Induction Hypothesis: Assume the property holds for each of the elements
in the set.
3. Induction step: Show the property holds when applying the rule(s)to compose
new elements.
EXAMPLE.
A language defined by BNF is a good example of a recursively enumerated set.
BNF definition of the language of expressions:
<expr> ::= <term> | <expr> + <term>
<term> ::= <element> | <term> * <element>
<element> ::= <num> | <var>
Prove that for all expressions the number of operators is always less than
the number of operands. Ex:
5 * Z + 30 + 7 <= 3 operators and 4 operands
1. Basis: The property P holds for <num> and <var>: n_rands =1 and n_rators = 0.
Since <term> is an <element> and <element> is a <num> or a <var>, P holds
for <term> and <element>. Thus, P holds for all nondecomposable elements.
2. Induction Hypothesis: Assume the property holds for each of the elements
currently in the set.
3. Induction step: Show the property holds for the next element added to
the set for each recursive rule.
Rule 1.
<expr> ::= <expr>[2] + <term>
By the induction hypothesis, P holds for <expr>[2] and <term>,
thus n_rators is less than n_rands in both cases. Given this, n_rators + 1
must be less than n_rands + 2, and P holds for <expr>.
Rule 2.
<term> ::= <term> * <element>
The same argument is made for this rule.
Given this BNF definition of a language of strings over the set {a,b,c}:
S ::= AB | AD
A ::= Aa | b
B ::= Bb | a
D ::= cDc | d
Prove that no string will ever begin with two b's.
Basis. There is no atomic element (a terminal) that begins with two b's.
True since true for the two atomic rules that involve b's:
A ::= b
B ::= a
Inductive Hypothesis. Assume no element used to compose new elements begins
with two b's.
Inductive Step. Given IH, how no composite element begins with two b's.
Rule 1.
A ::= Aa
By the inductive hypothesis A cannot begin with two b's, thus Aa cannot
begin with two b's.
Rule 2.
B ::= Bb
By the inductive hypothesis B cannot begin with two b's, thus Bb cannot
begin with two b's.
Rule 3.
S ::= AB | AD
By the inductive hypothesis A cannot begin with two b's, thus AB and AD
cannot begin with two b's.
Thus, no Sentence S can begin with two b's.
/////////// More Structural Induction Problems
EXAMPLE 1.
Give a recursive definition of the function "ones(s)", which counts the
number of ones in a bit string s.
Define a function head(s) that returns the first bit in s, tail(s) as a
function that returns all bits past the first bit, and s = head(s) + tail(s).
ones(s) = if s = null then 0 else head(s) + ones( tail(s) )
b) Use structural induction to prove that ones(st) = ones(s) + ones (t).
I.e., the number of 1s in the concatentation of bit strings s and t is
the number of 1s in s + the number of 1s in t.
Basis: For s=t=null, ones(null) = 0 and (ones(null)= 0 + ones(null)= 0) = 0.
Induction Step: The only way to add a 1 to st is to add a 1 to s or to add
a 1 to t. If you add a 1 to s then ones(s) is increased by 1 and ones(st)
is increased by 1. The same argument can be made for t.
EXAMPLE 2.
Use structural induction to show that l(t), the number of leaves of a
full binary tree T, is 1 more than i(T), the number of internal vertices
of T.
Ex. x l(t) = 8
/ \ i(t) = 7
x x
/ \ / \
x x x x
/\ /\ /\ / \
x x x x x x x x
Call this proposition P.
Definition of a full tree:
Tree ::= node | Tree[1] node Tree[2], where Size(Tree[1] =
Size(Tree[2])
Induction. Show that P holds for each rule in which you construct a tree.
Tree ::= leaf
P holds because this tree has 1 leaf and 0 vertices.
Tree ::= Tree[1] leaf Tree[2]
Assuming that the first rule holds, show that this rule holds.
Since the Size of both subtrees are the same this is true:
l(Tree[1]) = l(Tree[2]) = n_leaves
i(Tree[1]) = i(Tree[2]) = n_vertices
When you construct Tree from Tree[1] and Tree[2] you get this:
A. l(Tree) = 2 * n_leaves
B. i(Tree) = 2 * n_vertices + 1
By the induction hypothesis, this is true:
n_leaves = 1 + n_vertices.
Thus, you can replace n_leaves by n_vertices + 1 in Equation A:
A. l(Tree) = 2 * (1 + n_vertices)
= 2 + 2 * n_vertices <== this is the number of leaves
B. i(Tree) = 1 + 2 * n_vertices
Thus, the number of leaves is 1 more than the number of vertices. QED.
EXAMPLE 3.
Use structural induction to show that, given the following BNF definition of
a bit string, a string will never contain an even number bits.
BitStr ::= BitStr10 | 0 | 1
Show that P holds for each atomic element.
BitStr ::= 0 | 1
P obviously holds if a BitStr is a single bit.
Show that given P holds for each atomic element P holds for each each rule
by which you construct elements.
BitStr ::= BitStr10
The first time this rule is applied BitStr contains 3 bits. Thereafter,
the only way a BitStr is composed is to add 2 bits to an existing bit
string. Since n + 2 will always result in an odd number if n is odd, the
size of BitStr will always be odd. QED.
EXTERNAL/INTERNAL NODE RELATIONSHIP IN TREES
Given a full binary tree (full meaning a node has either no children or two
children), let n be the height of the tree, E be the number of external
(leaf) nodes and I be the number of internal (non-leaf) nodes. Let P be the
proposition that for a tree of height >= 0, the number of external nodes
is equal to the number of internal nodes plus 1. P is expressed here:
P(n): E = I + 1.
By definition, for height 0, E=1 and I=0. In the tree below of height 2,
there are 2 internal nodes and 3 external nodes:
o
/ \ P(2): 3 = 2 + 1.
o o
/ \
o o
You can use strong induction to prove that P holds for all trees, height
n >= 0 since a tree of height n has a left subtree of height < n and a
right subtree of height < n. The proof is started here:
Basis: P(0): 1 = 0 + 1. (a tree of height 0 has 1 external node). check.
IH. Assume P(k) and P(1)..P(k-1): P holds for trees height 1 to k.
IS. Show P(k+1): P holds for a tree of height k+1, assuming P(k) ... P(0).
P(k+1): E_(k+1) = I_(k+1) + 1. # SHOW THIS
To use strong induction, reason as follows. Let T be a tree of height k+1.
We know T is constructed of subtrees S1 and S2. When we construct T, we
know the external nodes of T will be the external nodes of S1 + S2. Thus,
E_(k+1) = E_S1 + E_S2.
By the way trees are constructed we know the internal nodes of T will be
the sum of the internal nodes of T's two subtrees plus 1 for T's root node:
I_(k+1) = I_S1 + I_S2 + 1.
We can now re-express P(k+1) by plugging in the above two equations:
Show: (E_S1 + E_S2) = (I_S1 + I_S2 + 1) + 1.
Since the subtrees of T are of height <= k, IH we know
E_S1 = I_S1 + 1.
E_S2 = I_S2 + 1.
Replacing E_S1 and E_S2 with these equations we have:
(I_S1 + 1) + (I_S2 + 1) = (I_S1 + I_S2 + 1) + 1.
Simplify.
I_S1 + I_S2 + 2 = I_S1 + I_S2 + 2. bingo.