Report

Section 3.4 Recursive Definitions 1 Recursion • Recursion is the process of defining an object in terms of itself • Technique can be used to define sequences, functions and sets • To recursively define a sequence: – give first term – give rule for defining subsequent terms from previous terms 2 Recursively Defined Functions • Specify f(0) • Give a rule for finding f from f’s value at smaller integers 3 Example 1 • Define f recursively by: f(0) = 3 f(n+1) = 2(f(n)) + 3 • Find f(1), f(2), f(3) and f(4) f(1) = 2(f(0)) + 3 = 9 f(2) = 2(f(1)) + 3 = 21 f(3) = 2(f(2)) + 3 = 45 f(4) = 2(f(3)) + 3 = 93 4 Example 2: give a recursive definition of the factorial function • Define f(0): f(0) = 1 • Define rule for f(n+1) from f(n): – Since (n+1)! = n!(n+1) – then f(n+1) = (n+1)(f(n)) • For example, to find f(5) = 5! Do: f(5) = 5(f(4)) = 5(4(f(3))) = 5(4(3(f(2)))) = 5(4(3(2(f(1))))) = 5(4(3(2(1(f(0))))))) = 5*4*3*2*1*1 = 120 5 Example 3 • Give recursive definition for the sum of the first n positive integers • Define f(0) = 0 • Then f(n+1) = n+1+f(n) • Thus f(4), for example, is: 4+f(3) = 4+3+f(2) = 4+3+2+f(1) = 4+3+2+1+f(0) = 4+3+2+1+0 = 10 6 Example 4 • Give recursive definition of an where a is a non-zero real number and n is a nonnegative integer • Define a0 = 1 • Then define an+1 = a(an) • So x5 = x(x4) = x(x(x3)) = x(x(x(x2))) = x(x(x(x(x1)))) = x(x(x(x(x(x0) = x*x*x*x*x*1 7 Example 5: summation • Give a recursive definition of: n ak k=0 • Basis: n ak = a0 k=0 • Inductive: n+1 n k=0 k=0 ak = an+1 + ak 8 Example 6 • Give recursive definition of Pm(n), product of integer m and non-negative integer n • Basis: Pm(0) = 0 • Inductive: Pm(n+1) = Pm(n) + m • So, for example, 4*3 = P4(3) = P4(2)+4 = P4(1)+4+4 = P4(0)+4+4+4 = 0+4+4+4 = 12 9 Fibonacci numbers • Fibonacci numbers are defined by: f0 = 0, f1 = 1, fn = fn-1 + fn-2 where n=2,3,4 … So f2 = f1 + f0 = 1 f3 = f2 + f1 = 2 f4 = f3 + f2 = 3 f5 = f4 + f3 = 5 f6 = f5 + f4 = 8 etc. 10 Example 7: Fibonacci numbers • The recursive definition of Fibonacci numbers can be used to prove many properties of these numbers. For example: fn > n-2 where = (1 + 5) / 2 whenever n 3 Let P(n) = fn > n-2 ; we wish to show that P(n) is true for n 3 11 Example 7 • Note that: < 2, 2 = f3 (f3 > 3-2) 2 = ((1+5)/2)((1+5)/2) = (1+25+5)/4 = (2(5+3))/(2*2) = (3 + 5) / 2 (3 + 5) / 2 < 3, 3 = f4 (f4 > 4-2) • So P(n) is true for n=3 and n=4 12 Example 7 • Assume P(k) is true, so fk > k-2 for all integers k with 3 <= k <= n, with n 4 • Show P(n+1) is true: fn+1 > n-1 • By the quadratic formula: x=(-bb2-4ac)/2a is a solution for x2-x-1=0 so 2 = + 1 13 Example 7 • Thus, n-1 = 2(n-3) = (+1) n-3 = (n-3) +1(n-3) = (n-2 + n-3) • By the inductive hypothesis, if n5, it follows that fn-1 > n-3, fn > n-2 • So we have: fn+1 = (fn + fn-1) > (n-2 + n-3) = n-1, completing the proof 14 Example 8 • Prove that f1+f3+ … +f2n-1 = f2n whenever n is a positive integer • Basis: f1 = f2*1 true, since f1 = f2 = 1 • We want to prove: f1+f3+ … f2n-1+f2n+1=f2(n+1) 15 Example 8 • Assume P(n) is true; then: f1+f3+ … f2n-1+f2n+1 = f2n + f2(n+1) f2n + f2(n+1) = f2n+2 • Recall the definition of Fibonacci numbers: fn = fn-1 + fn-2 • So the theorem is true 16 Recursively defined sets • Sets may be recursively defined as follows: – an initial collection of elements is given – rules used to construct elements of the set from other elements are given • Such sets are well-defined, and theorems about them can be proved using their recursive definitions 17 Example 9 • S is recursively defined by: 3S (x+y) S if x S and y S • Show that S is the set of all positive integers divisible by 3 18 Example 9: Proof • Let A = {x | x is divisible by 3} (or, x=3n) • To prove A=S, show that AS and SA • Proving AS by mathematical induction: – P(n): 3n belongs to S – Basis: 3*1 S - true by definition of S – Inductive: Since we already know 3 S (by definition), and (3n+3) S (also by definition) and 3n+3 = 3(n+1), AS is proven 19 Example 9: Proof • To prove SA, use recursive definition of S: – Basis: 3 S (by definition) – Since 3 = 3*1, all elements specified by the definition’s basis step are divisible by 3 • To complete proof, must show all integers generated by using second part of definition of S are in A 20 Example 9: Proof • To do this, show that x+y is in A when xS and yS and xA and yA • If x A and y A, 3|x and 3|y - so 3|(x+y) • This completes the proof 21 Well-formed Formulae • Common application of the recursive definition of sets • Example: well-formed formulae of variables, numerals and operators from {+,-,*,/,} are defined by: – x is a well-formed formula is x is a numeral or variable; – (f+g), (f-g), (f*g), (f/g) and (fg) are well-formed formulae if f and g are well-formed formulae 22 Application of well-formed formulae • Using this definition, we can define any infix expression • For example, x and 5 are well-formed formulae • So (x+5), (x*5), etc. are well-formed formulae • And (x+5) / (x*5) is a well-formed formula 23 Example 10 • Well-formed formulae for compound propositions involving T, F, variables and operators {,,,,} are defined by: – T, F and p (where p is a propositional variable) are well-formed formulae; – (p), (p q), (p q), (p q), (p q) are wellformed formulae is p and q are well-formed – Thus, we could build any compound propositional expression in the same way as with infix arithmetic expressions 24 Recursive definition of strings • The set * of strings over the alphabet can be recursively defined by: – * where is the empty string and – wx * whenever w * and x • Translation: – empty strings belong to the set of strings – can produce new strings by concatenating strings from the set of strings with symbols from the alphabet 25 Recursive definition of strings • Can also recursively define the length of strings; if l(w) is the length of string w, then: – l() = 0 – l(wx) = l(w)+1 if w * and x • Can use these definitions in proofs 26 Example 11 • Prove that l(xy) = l(x) + l(y) where x * and y * • Basis: P() – show l(x) = l(x)+l() for x* – since l() = 0, l(x)+l() = l(x), so l(x) is true 27 Example 11 • Inductive step: – Assume P(y) is true; show that this implies P(ya) is true where a – Need to show l(xya) = l(x) + l(ya) – By recursive definition of l(w), we have l(xya)=l(xy+1) and l(ya) = l(y)+1 – By inductive hypothesis, l(xy)=l(x)+l(y) – So we conclude l(xya)=l(x)+l(y)+1 = l(x)+l(ya) 28 Section 3.3 Recursive Definitions - ends - 29