Recurrence RelationsRecursion and Mathematical InductionThe Towers of HanoiWhat if we knew we could solve part of the problem?Can we do one better?Solved for one more!Where do recurrence relations come from?Slide 8Can recurrence relations be solved?Solution TechniquesFirst stepGuessing solution and proving by inductionGuessing solution and proving by induction IIBack-substitutionRecursion TreesExample ProblemInduction ProofSlide 18Example Problem 2Recursion TreeMaster TheoremExampleCharacteristic Equation ApproachCharacteristic EquationSolving for constantsRepeated roots for char. eqnSlide 27Inhomogeneous EquationSlide 29Changing variableSlide 31Example: Up-down PermutationsExample: Towers of HanoiExample: Merge SortRecurrence Relations•Connection to recursive algorithms•Techniques for solving themRecursion and Mathematical InductionIn both, we have general and boundary conditions:The general conditions break the problem into smaller and smaller pieces.The initial or boundary condition terminate the recursion. Both take a Divide and Conquer approach to solving mathematical problems.The Towers of HanoiWhat if we knew we could solve part of the problem?Assume we can move k (in this case, 4) different ringsCan we do one better?Solved for one more!Where do recurrence relations come from?•Analysis of a divide and conquer algorithm–Towers of Hanoi, Merge Sort, Binary Search•Analysis of a combinatorial object –up-down permutations•This is the key analysis step I want you to master•Use small cases to check correctness of your recurrence relationRecurrence RelationsPossible recurrence relations:an = an-1 + 1; a1 = 1 => an = n (linear)an = an-1+ 2n - 1; a1=1 => an = n2(polynomial)an = 2an-1; a1 = 1 => an = 2n(exponential)an = n an-1; a1 = 1 => an = n! (others…)Can recurrence relations be solved?•No general procedure for solving recurrence relations is known, which is why it is an art. •However, linear, finite history, constant coefficient recurrences always can be solved•Example: an = 2an-1 + 2an-2 +1 ; a1 = 1 ; a2 = 1–degree = 1–history = 2–coefficients = 2, 2, and 1•In the end, what is the best way to solve this?–Software like Mathematica or Maple, but I still want you to be able to solve some on your own without such aidSolution Techniques•Guess a solution by looking at a few small examples and prove by induction.•Try back-substituting until you know what is going on.•Draw a recursion tree.•Master Theorem•General TechniqueFirst step•Using the base case and the recursive case, calculate small values•Use these values to help guess a solution•Use these values to help verify correctness of your closed form solutionGuessing solution and proving by inductionWe can use mathematical induction to prove that a general function solves for a recursive one.Tn = 2Tn-1 + 1 ; T0 = 0n = 0 1 2 3 4 5 6 7 8Tn= Guess what the solution is?Guessing solution and proving by induction IIProve: Tn = 2n - 1 by induction:1. Show the base case is true: T0 = 20 - 1 = 02. Now assume true for Tn-13. Substitute in Tn-1 in recurrence for TnTn = 2Tn-1 + 1 = 2 ( 2n-1 - 1 ) + 1 = 2n -1Back-substitutionExample: T(n) = 3T(n/4) + n, T(1) = 1 = 3(3T(n/16)+n/4) + n = 9T(n/16) + 3n/4 + n = 9(3T(n/64) +n/16) + 3n/4 + n = 27T(n/64)+9n/16 + 3n/4 + n ini?043Recursion TreesT(n) = 2 T(n/2) + n2 , T(1) = 1Example ProblemUse induction to prove that MergeSort is an O(n log n) algorithm. Mergesort(array)n = size(array)if ( n == 1) return arrayarray1 = Mergesort(array[1 .. n/2])array2 = Mergesort(array[n/2 .. n])return Merge(array1, array2)Induction ProofExample: Prove that T(n) = 2T( n/2 ) + n , T(1) = 1 is O(n log n).Base case: n=2, c>4.We need to prove that T(n) < c n log n , for all n greater than some value.Inductive step: Assume T(n/2) ≤ c (n/2) log (n/2) Show that T(n) ≤ c n log n .Induction ProofGiven : T(n/2) ≤ c (n/2) log (n/2)T(n) = 2T( n/2 ) + n≤ 2( c(n/2) log (n/2) ) + n≤ 2( c(n/2) log (n/2) ) + n (dropping floors makes it bigger!)= c n log(n/2) + n= c n ( log(n) - log(2) ) + n= c n log(n) - c n + n (log22 = 1)= c n log(n) - (c - 1) n< c n log(n) (c > 1)Example Problem 2T(n) = T(n/3) + T(2n/3) + nShow T(n) is (n log n) by appealing to the recursion tree.Recursion TreeMaster Theorem•T(n) = a T(n/b) + f(n)–Ignore floors and ceilings for n/b–constants a >= 1 and b>1–f(n) any function•If f(n) = O(nlog_b a-) for constant >0, T(n) = (nlog_b a)•If f(n) = (nlog_b a), T(n) =  (nlog_b a lg n)•If f(n) = (nlog_b a+) for some constant  >0, and if af(n/b) <= c f(n) for some constant c < 1 and all sufficiently large n, T(n) = (f(n)).•Key idea: Compare nlog_b a with f(n)Example•T(n) = 4 T(n/2) + n•a =•b =•nlog_b a =•f(n) =Characteristic Equation Approach•tn = 3tn-1 + 4tn-2 for n > 1–t0 = 0, t1 = 5•Rewrite recurrence–tn - 3tn-1 - 4tn-2 = 0•Properties–Homogeneous: no terms not involving tn–Linear: tn terms have no squares or worse–constant coefficients: 1, -3, -4Characteristic Equation•tn - 3tn-1 - 4tn-2 = 0•Rewrite assume solution of the form tn = xn•xn – 3xn-1 – 4xn-2 = 0•xn-2 (x2 – 3x – 4) = 0•Find roots of (x2 – 3x – 4)–(x+1)(x-4)  roots are -1 and 4•Solution is of form c1(-1)n + c24nSolving for constants•tn = c1(-1)n + c24n•Use base cases to solve for constants–t0 = 0 = c1(-1)0 + c240 = c1 + c2–t1 = 5 = c1(-1)1 + c241 = -c1 + 4c2–5c2 = 5  c2 = 1  c1 = -1•tn = (-1)n+1 + 4n•Always test solution on small values!Repeated roots for char. eqn•tn - 5tn-1 + 8tn-2 – 4tn-3= 0–boundary conditions: tn = n for n = 0, 1, 2•x3 - 5x2 + 8x – 4 = 0•(x-1)(x-2)2  roots are 1, 2, 2•Solution is of form c1(1)n + c22n + c3n2n–If root is repeated third time, then n22n term, and so onSolving for constants•tn = c1(1)n + c22n + c3n2n•Use base cases to solve for constants–t0 = 0 = c1(1)0 + c220 + c30 20 = c1 + c2–t1 = 1 = c1(1)1 + c221 + c31 21 = c1 + 2c2 + 2c3–t2 = 2 = c1(1)2 + c222 + c32 22 = c1 + 4c2 + 8c3–c1 = -2, c2 = 2, c3 = -1/2•tn = 2n+1 – n2n-1 – 2•Test the solution on small values!Inhomogeneous Equation•tn - 2tn-1 = 3n–base case value for t0 only•(x – 2) (x-3) = 0–(x-2) term comes from homogeneous solution–If