1 V Adamchik Recurrences Victor Adamchik Fall of 2005 Plan 1 More on multiple roots 2 Inhomogeneous equations 3 Divide and conquer recurrences Multiple roots In the previous lecture we have showed that if the characteristic equation has a multiple root then both n an and an n n are solutions Today we will prove this directly Consider the second order recurrence equation an an an 1 2 The characteristic equation 2 has two identical roots 1 0 2 2 1 2 if and only if 4 4 2 It follows 2 2 2 4 2 To prove that an n n is the solution we substitute this into the original recurrence n n Divide this by n n 1 1 n 2 n 2 n 2 n 2 n 1 n 2 0 V Adamchik 21 127 Concepts of Mathematics and then collect terms with respect to n n The first term is zero because 2 is zero because and 4 Theorem Let 2 2 0 is the roots of the characteristic equation The second term 2 be a root of multiplicity p of the characteristic equation Then n n n n2 n n p 1 n 3 an an 3 are all solutions to the recurrence Example Find a general solution an 3 an The characteristic equation has a root 1 2 1 of multiplicity 3 Therefore an c1 c3 n2 c2 n is a solution of this recurrence equation Exercise Solve the recurrence an 5 an 1 7 an a0 1 a1 2 3 an 2 a2 3 0 3 Inhomogeneous Equations As an example of such recurrences we consider Fibonacci trees This data structure is defined recursively as follows the empty tree is a Fibonacci tree of order 0 a single node tree is a Fibonacci tree of order 1 a Fibonacci tree of order n has a left Fibonacci subtree of order n 1 and a right Fibonacci subtree of order n 2 V Adamchik 3 We want to count the number of nodes in a Fibonacci tree of order n Let Tn denote the number of nodes in a tree of order n Then Tn Tn T0 Tn 1 1 2 0 T1 1 A recurrence of the form an 1 an 1 k an f n k where all k are constants and f n is a function other than the zero is called an inhomogeneous linear recurrence equation with constant coefficients There is no a known general method for solving such equations We consider a one important particular case when the function f n is n f n pn where p n is a polynomial and 0 The main idea is to transform a given inhomogeneous equation into a homogeneous one Let us trace the idea on the Fibonacci tree recurrence In order to cancel the right hand side we consider the original equation along with the one obtained by replacing n n 1 Tn Tn Tn 1 Tn 1 Tn 2 Tn 1 2 3 1 3 0 Next we subtract the second equation from the first Tn T0 2 Tn 0 T1 1 Tn 1 T2 2 V Adamchik 21 127 Concepts of Mathematics This is the forth order homogeneous equation which we can solve by the characteristic equation Solve x 3 x 2 x 2 1 x 1 2 1 0 x 1 5 1 2 x 1 5 The general solution is given by Tn c1 1 c2 n 5 1 c3 2 5 n 2 The system for coefficients ck T0 c1 c2 c3 T1 c1 c2 1 T2 c1 c2 1 2 2 0 5 1 c3 2 5 c3 2 1 5 2 1 2 5 2 has a solution c1 5 1 c2 3 5 c3 10 3 5 10 5 After some algebra we get Tn 1 1 5 1 1 5 n 1 2 5 1 5 1 5 2 5 n 1 1 1 2 n 5 n 1 2 5 which can be recognized as Tn Fn Fn 1 1 or Tn Fn 2 1 wherer Fn is the Fibonacci number You will see this sequence again in 15 211 when study AVL trees V Adamchik 5 Divide and conquer Recurrences The divide and conquer algorithm consist of three steps dividing a problem into smaller subproblems solving recursively each subproblem then combining solutions Suppose Tn is the number of steps in the worst case needed to solve the problem of size n Let us split a problem into a 1 subproblems each of which is of the input size bn where b 1 Observe that the number of subproblems a is not necessarily equal to b The total number of steps Tn is obtained by all steps needed to solve smaller subproblems Tn b plus the number needed to combine solutions into a final one The following equation is called divide and conquer recurrence relation Tn f n a Tn b Here are some examples Tn 2 Tn 2 n Tn 3 Tn 4 n2 Tn Tn 3 n log n There are three main techniques to solve such recurrence equations the iteration method the tree method the master theorem method MergeSort Mergesort involves the following steps Divide the array into two subarrays Sort each subarray Merge them into one in a smart way Example 27 10 12 25 34 16 15 31 1 divide it into two parts 27 10 12 25 2 sort each one 34 16 15 31 V Adamchik 21 127 Concepts of Mathematics 10 12 25 27 15 16 31 34 3 merge into one comparing one by one the paired elements from the two parts 10 15 12 15 25 15 25 16 25 31 31 27 31 34 10 12 15 16 25 27 31 34 Let Tn denote the running time of the algorithm i e the number of comparisons needed to sort n elements We have the following recurrence equation for Tn Tn n 2 T n2 T1 1 0 To get the feeling for the nature of the solution we consider a case when n is a power of 2 namely n 2k Then 2 T2k T2k 2k 1 1 We divide both sides by 2k and iterate it T2k 1 2k 1 T2k 2 2k 2 T2k 2k T2k 1 2k 1 1 2k 1 1 1 2k 1 k steps T1 20 T2 2 1 2 1 Using a backward substitution this leads to T2k 2k 1 1 2k T2k 2k k 1 1 2k 1 2k 1 1 2k 1 The finite sum is the geometric series k j 0 Therefore xj xk 1 1 x 1 1 1 2 1 2 V Adamchik 7 k j 1 1 2j k 1 j 0 1 2j 1 1 k 1 2 1 1 2 Thus T2k 2k k 1 1 2k or T2k Since n k 1 2k 1 2k we finally obtain Tn n log n n 1 1 1 1 2k