Report

Recursive Definitions Rosen, 3.4 Recursive (or inductive) Definitions • Sometimes easier to define an object in terms of itself. • This process is called recursion. – Sequences • {s0,s1,s2, …} defined by s0 = a and sn = 2sn-1 + b for constants a and b and n Z+ – Sets • 3 S and x+y S if xS and yS – Functions • Example: f(n) = 2n, f(n) = 2f(n-1) and f(0) = 1 Recursively Defined Functions To define a function with the set of nonnegative integers as its domain 1. Specify the value of the function at zero (or sometimes, it first k terms). 2. Give a rule for finding its value at an integer from its values at smaller integers. Examples of Recursively Defined Functions • Factorial Function n! n! = n(n-1)(n-2)….(1) f(0) = 1, f(n) = n(f(n-1)) • an f(0) = 1, f(n+1) = f(n)*a • Fibonacci Numbers f0=0, f1=1, f n+1 = fn + f n-1 {0,1,1,2,3,5,8,13,...} Prove that the nth term in the Fibonacci n 2 sequence is 1 f i when n2 i 0 Induction Proof: 2 2 Basic Step: Let n = 2, then f2 = 1 = 1 f i =1+0 i 0 Inductive Step: Consider k2 and assume that the expression is true for 2 n k. We must show k1 that the expression is true for (1 f i ) n = k+1, i.e., that fk+1 i 0 fk+1 = fk +fk-1 by definition k 2 (1 f i ) f k 1 i 0 by the inductive hypothesis Fibonacci Proof (cont.) k 2 (1 f i ) f k 1 i 0 k1 (1 f i ) i 0 Since f2 is true and [fn is true for 2 n k fk+1] is true, then fn is true for all positive integers n2. Recursively Defined Set Example Let the set S be defined recursively as 3 S and x+y S if xS and yS. Prove that S is equal to the set of positive integers divisible by 3 (set A). Proof: To show that S = A, we must show that AS and that SA. Recursive Set Example (cont.) First we will show that A S. To do this we must show that every positive integer divisible by 3 is in S. This is the same as saying that 3n is in S for nZ+. We will do an inductive proof. Let p(n) be the statement that 3nS for n a positive integer. Basis Step: p(1) = 3(1) = 3 Inductive Step: We will show that p(n) p(n+1) Let p(n) S. Then p(n+1) = 3(n+1) = 3n + 3. Since 3nS and 3S, then 3n+3S. Therefore every element in A must be in S. Recursive Set Example (cont.) Now we will show that SA. To do this we must show that every element in S is divisible by 3, i.e., that it can be represented as 3(j) where j is a positive integer. Basis Step: 3A since 3 = 3(1) Inductive Step: Assume x,y are in A (where x,y S). x and y are divisible by 3 since they are both in A. Therefore x = 3j and y = 3k for j,k Z+. Then z = x+y = 3j+3k = 3(j+k), which is divisible by 3, so z A (and by definition, z S). Therefore every element in S must be in A Prove fn > n-2 where = (1+5)/2 whenever n3 Inductive Proof Basis Step: First we will show fn > n-2 for f3 and f 4. 3-2 = 1 = (1+5)/2 < (1+9)/2 = 4/2 = 2 = f3 4-2 = 2 = [(1+5)/2]2 = (1+ 25 + 5)/4 = (6+ 25)/4 = 3/2 + 5/2 < 3/2 + 9/2 = 3 = f4 fn > n-2 (cont.) Inductive Step: Assume that fk > k-2 is true for all nonnegative integers 3 k n when n>4 . We must show that fn+1> n-1. Lemma: 2 = [(1+5)/2]2 = (1+25 +5)/4 = 3/2 + (5)/2 = 1 + (1+5)/2 = 1+ fn > n-2 (cont.) n-1 = 2n-3 = (+1)(n-3) = n-2+n-3 By our inductive hypothesis fn-1 > n-3 and fn > n-2 fn+1= fn + fn-1 > n-2+n-3 = n-1 Since f3 and f3 are true and fk is true for 3 k n fn+1 is true, then fn is true for all positive integers n3 Find a closed form solution to the recursive equation: T(n) = T(n-1) + c1. T(0) = c0 One approach is to write down several terms, guess what the equation is, and then prove that your guess is correct (or not) using an induction proof. T(0) = c0 T(1) = T(0) + c1 = c0 + c1 T(2) = T(1) + c1 = c0 + 2c1 T(3) = T(2) + c1= c0 + 3c1 T(4) = T(3) + c1= c0 + 4c1 Guess that T(n) = c0 + nc1 Induction proof Basis Step: for n = 0, T(0) = c0 + (0)c1 = c0 Inductive Step: Assume that T(n) = c0 + nc1, we must show that T(n+1) = c0 + (n+1)c1. T(n+1) = T(n) + c1 = c0 + nc1 + c1 = c0 + (n+1)c1. Find a closed form solution to T(1) = c0, T(n) = 2T(n-1)+c1 T(1) = c0 T(2) = 2T(1) + c1 = 2c0 + c1 T(3) = 2T(2)+c1 = 2(2c0+c1)+c1 = 4c0+3c1 T(4) = 2T(3)+c1 = 2(4c0+3c1)+c1 = 8c0+7c1 T(5) = 2T(4)+c1 = 2(8c0+7c1)+c1 = 16c0+15c1 Guess that T(n) = 2n-1c0 + (2n-1-1)c1 Prove that T(1) = c0, T(n) = 2T(n-1)+c1has closed form solution T(n) = 2n-1c0 + (2n-1-1)c1 Basis Step: T(1) = 21-1c0 + (21-1-1)c1 = c0 Induction Step: Assume that T(n) = 2n-1c0 + (2n-1-1)c1. We must show that T(n+1) = 2(n+1)-1c0 + (2(n+1)-1-1)c1 = 2nc0 + (2n-1)c1. T(n+1) = 2T(n) + c1 = 2[2n-1c0 + (2n-1-1)c1]+ c1 = 2nc0 + (2n-2)c1 + c1 = 2nc0 + 2nc1 - c1 = 2nc0 + (2n-1)c1.