5.3 Recursive Definitions and Structural Induction

Recursively Defined Functions • Definition ○ A recursive or inductive definition of a function consists of two steps. ○ Basis Step § Specify the value of the function at zero. ○ Recursive Step § Give a rule for finding the at an integer from its values at smaller integers ○ A function f(n) is the same as a sequence a_0,a_1,… where f(i)=a_i ○ This was done using recurrence relations in Section 2.4 • Example 1 ○ Suppose f is defined by § f(0)=3 § f(n+1)=2f(n)+3 ○ Find f(1), f(2), f(3), f(4) § f(1)=2f(0)+3=2∙3+3=9 § f(2)=2f(1)+3=2∙9+3=21 § f(3)=2f(2)+3=2∙21+3=45 § f(4)=2f(3)+3=2∙45+3=93 • Example 2 ○ Give a recursive definition of the factorial function n! ○ f(0) = 1 ○ f(n + 1) = (n + 1)∙ f(n) • Example ○ Give a recursive definition of ∑_(k=0)^n▒a_k ○ The first part of the definition is § ∑_(k=0)^0▒a_k =a_0 ○ The second part is § ∑_(k=0)^(n+1)▒a_k =(∑_(k=0)^n▒a_k )+a_(n+1) Fibonacci Numbers • The Fibonacci numbers are defined as follows: ○ f_0=0 ○ f_1=1 ○ f_n=f_(n−1)+f_(n−2) • Find f_2,f_3,f_4,f_5 ○ f_2=f_1+f_0=1+0=1 ○ f_3=f_2+f_1=1+1=2 ○ f_4=f_3+f_2=2+1=3 ○ f_5=f_4+f_3=3+2=5 • Show that whenever n ≥ 3, f_n α^(n−2), where α=(1+√5)/2 ○ Let P(n) be the statement f_n α^(n−2) . ○ Use strong induction to show that P(n) is true whenever n≥3. ○ Basis step § P(3) holds since α 2 = f_3 § P(4) holds since α^2 = (3+√5)/2 3 = f_4 ○ Inductive step § Assume that P(j) holds § i.e., f_j α^(j−2) for all integers j with 3 ≤ j ≤ k, where k ≥ 4. § Show that P(k+1) holds, i.e., f_(k+1) α^(k−1). § Since α^2= α + 1 (because α is a solution of x^2−x−1=0), § α^(k−1)=α2⋅α^{(k−3)=(α+1)⋅α}(k−3)=α⋅α^{(k−3)+1⋅α}(k−3)=α^(k−2)+α(k−3) § By the inductive hypothesis, because k ≥ 4 we have □ f_(k−1) α^(k−3) □ f_k α^(k−3) § Therefore, it follows that □ f_(k+1)=f_k+f_(k−1) α^(k−2)+α(k−3)=α^(k−1) § Hence, P(k+1) is true. Lamé’s Theorem • Lamé’s Theorem ○ Let a and b be positive integers with a≥b. ○ Then the number of divisions used by the Euclidian algorithm to find gcd(a,b) ○ is less than or equal to five times the number of decimal digits in b. • Proof ○ When we use the Euclidian algorithm to find gcd(a,b) with a≥b, ○ n divisions are used to obtain (with a=r_0,b=r_1) § r_0=r_1 q_1+r_2, 0 r_2 r_1 § r_1=r_2 q_2+r_3, 0 r_3 r_2 § ⋮ § r_(n−2)=r_(n−1) q_(n−1)+r_n, 0 r_n r_(n−1) § r_(n−1)=r_n q_n ○ Since each quotient q_1,q_2,…,q_(n−1) is at least 1 and q_n≥2 § r_n≥1=f_2 § r_(n−1)≥2r_n≥2f_2=f_3 § r_(n−2)≥r_(r−1)+r_n≥f_3+f_2=f_4 § ⋮ § r_2 r_3+r_4≥f_(n−1)+f_(n−2)=f_n § b=r_1≥r_2+r_3≥f_n+f_(n−1)=f_(n+1) ○ If n divisions are used to find gcd(a,b) with a≥b, then b ≥ f_(n+1) ○ By Example 4, f_(n+1) α^(n−1), for n 2, where α=(1+√5)/2. ○ Therefore, b α^(n−1). ○ Because log_10⁡α ≈ 0.208 1/5, log_10⁡b (n−1) log_10⁡α (n−1)/5 ○ Hence, n−1 5⋅log_10⁡b ○ Suppose that b has k decimal digits. Then b 10k and log_10⁡b k. ○ It follows that n−1 5k and since k is an integer, n≤5k. ○ Therefore, O(log b) divisions are used to find gcd(a,b) whenever a b. ○ The number of divisions needed is less than or equal to 5⋅(log_10⁡b+1) ○ Since the number of decimal digits in b is less than or equal to log_10⁡b+1 Recursively Defined Sets and Structures • Recursive definitions of sets have two parts: ○ The basis step specifies an initial collection of elements. ○ The recursive step gives the rules for forming new elements in the set from those already known to be 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 always assume that the exclusion rule holds, even if it is not explicitly mentioned. • Example: Subset of Integers S ○ Basis step: 3 ∊ S. ○ Recursive step: If x ∊ S and y ∊ S, then x+y is in S. ○ Initially 3 is in S, then 3 + 3 = 6, then 3 + 6 = 9, etc. • Example: The natural numbers N. ○ Basis step: 0 ∊ N. ○ Recursive step: If n is in N, then n + 1 is in N. ○ Initially 0 is in N, then 0 + 1 = 1, then 1 + 1 = 2, etc. Strings • Definition: The set Σ* of strings over the alphabet Σ: ○ Basis step: λ ∊ Σ* (λ is the empty string) ○ Recursive step: If w is in Σ* and x is in Σ, wx∈Σ^∗. • Example ○ If Σ = {0,1} ○ The strings in in Σ* are the set of all bit strings, λ, 0, 1, 00,01,10, 11, etc. • Example ○ If Σ = {a,b}, show that aab is in Σ*. ○ Since λ ∊ Σ* and a ∊ Σ, a ∊ Σ*. ○ Since a ∊ Σ* and a ∊ Σ, aa ∊ Σ*. ○ Since aa ∊ Σ* and b ∊ Σ, aab ∊ Σ*. String Concatenation • Two strings can be combined via the operation of 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: ○ Basis step § If w∈Σ^∗, then w⋅λ=w ○ Recursive step § If w_1∈Σ^∗ and w_2∈Σ^∗ and x∈Σ^∗ then w_1⋅(w_2 x)=(w_1⋅w_2 )x • Often w_1⋅w_2 is written as w_1 w_2. • If w_1 = abra and w_2 = cadabra, the concatenation w_1 w_2 = abracadabra. Length of a String • Give a recursive definition of l(w), the length of the string w. • The length of a string can be recursively defined by: ○ l(λ)=0 ○ l(wx) = l(w) + 1 if w∊Σ* and x∈Σ Rooted Trees • The set of rooted trees, where a rooted tree consists of ○ a set of vertices containing a distinguished vertex called the root ○ edges connecting these vertices • can be defined recursively by these steps • Basis step ○ A single vertex r is a rooted tree. • Recursive step ○ Suppose that T_1,…,T_n are disjoint rooted trees with roots r_1,…,r_n respectively. ○ Then the graph formed by § start with a root r, which is not in any of the rooted trees T_1,…,T_n § add an edge from r to each of the vertices r_1,…,r_n ○ is also a rooted tree. Full Binary Trees • The set of full binary trees can be defined recursively by these steps. ○ 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 T_1∙T_2, consisting of □ a root r □ edges connecting the root to each of the roots of T_1 and T_2 • 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=T_1⋅T_2 has height § h(T)=1+max⁡(hT_1 ),hT_2 )) • The number of vertices n(T) of a full binary tree T is defined recursively as follows ○ Basis step § n(T)=1 for full binary tree T consisting of only a root r ○ Recursive step § If T_1 and T_2 are full binary trees § Then the full binary tree T=T_1⋅T_2 has the number of vertices § n(T)=1+n(T_1 )+n(T_2 ) Structural Induction • To prove a property of the elements of a recursively defined set, we use structural induction • Basis step ○ Show that The result holds for all elements specified in the basis step • Recursive step ○ Suppose the statement is true for each of the elements used to construct new elements in the recursive step of the definition ○ Show that the result holds for these new elements. • The validity of structural induction can be shown to follow from the principle of mathematical induction. Structural Induction and Binary Trees • If T is a full binary tree, then n(T)≤2^(hT)+1)−1 • Proof: Use structural induction • Basis step ○ The result holds for a full binary tree consisting only of a root ○ n(T) = 1 and h(T) = 0 ○ Hence, n(T) = 1 ≤ 2^(0+1)−1 = 1 • Recursive step ○ Assume n(T_1 )≤2^(hT_1 )+1)−1 and n(T_2 )≤2^(hT_2 )+1)−1 for full binary trees T_1,T_2 ○ n(T)=1+n(T_1 )+n(T_2 ) ○ ≤1+(2^(hT_1 )+1)−1)+(2^(hT_2 )+1)−1) ○ ≤2⋅max⁡(2^(hT_1 )+1),2^(hT_2 )+1) )−1 ○ =2⋅2^max⁡〖(h(T_1 ),hT_2 ))+1〗 −1 ○ =2⋅2^ht) −1 ○ =2^(ht)+1)−1