1 V Adamchik Recursions Victor Adamchik Fall of 2005 Plan 1 Recurrence relations 2 Solving First Order Linear Recurrences Recurrence relations Definition If n th term of a sequence can be expressed as a function of previous terms xn f xn k xn k 1 xn 1 n k then this equation is called a recurrence relation The values x1 x2 xk must be explicitely given They are called initial conditions The function f in the definition above may depend upon all or some previous terms In this lecture we will we will outline some methods of solving recurrence relation By solving we mean to find an explicit form of xn as a function of n that is free of previous terms except ones given in initial conditions For example the Towers of Hanoi recurrence relation xn 2 xn x1 1 1 1 has the explicit solution 2n xn 1 Recurrences are classified by the way in which terms are combined Here is a list of some of the recurrences First Order Linear an Non Linear an 2 an 1 1 an 1 1 1 V Adamchik 21 127 Concepts of Mathematics Second Order Linear an an 1 an Non Linear an an 1 an 1 an 2 2 2 Higher Order an an an a0 an a1 an 1 an 3 2 an 1 a0 Divide and Conquer Binary Search an Merge Sort an a a 1 n 2 a n 2 n 2 n Solving First Order Linear Recurrences This class of recurrences can be solved by iteration also called telescoping namely apply the recurrence to itself until only initial values left In this section we consider the following classes of linear recurrence relations an an an n an an an n 1 an 1 n 1 an n 1 The first two equations are called homogeneous The last two equations are called inhomogeneous an an 1 Let us start with the equation an 2 an a1 1 1 The process of iteration is presented as follows an an an 1 2 2 an 1 2 an 2 2 an 3 V Adamchik 3 2 a1 a2 Performing back substitution we obtain an 2 an 1 22 an 23 an 2 3 Hence 2n an 1 Theorem 1 The recurrence an an 1 has the following solution n 1 an an n an a1 1 Theorem 2 The recurrence n an an 1 has the following solution n an a1 k k 2 For example if n n the solution is an a1 n Exercise Solve the recurrence an n n 1 an 1 1 1 a1 an an n As an example of the inhomogeneous type we consider an an 1 a1 1 n Applying the recurrence to itself an an an 1 2 an an an 1 2 3 n n n 1 2 2n 1 a1 V Adamchik 21 127 Concepts of Mathematics a1 a2 2 and performing back substitution an an 1 n an n 2 n 1 an 3 n 2 n 1 n 2 1 we obtain an n n 1 1 n n 1 2 an Theorem 3 The recurrence an an n n 1 1 has the following solution an n a1 n 1 2 2 n an a1 k k 2 an an n 1 The Towers of Hanoi recurrence relation 2 an 1 a1 1 an 1 We proceed in the same way as above First we use iteration 2 an 2 an 2 an 2 a1 an an an 1 2 a2 1 1 1 1 2 3 1 and then back substitution an 2 an 22 an 1 1 2 2 23 an 1 22 3 2 The solution is 2n an or since a1 1 a1 2n 2 2n 2n 1 1 2 1 1 an 2n 1 2n 2 2 1 2n 1 V Adamchik 5 Let us consider the most general case an an 1 n an an 1 n By iteration we get 2 an an 3 an an 2 3 n 2 n 1 2 n n 1 n The pattern is obvious Theorem 4 The recurrence an an n 1 has the following solution n 1 an n a1 n k k k 2 Exercise Solve the recurrence an an n an 1 2n 2 an 1 a0 1 n The explicit solution in this case is left as an exercise to the reader Exercise Solve the recurrence an n n 1 a1 an 1 n2 1 Note Solving recurrence equations by iteration is not a method of proof Therefore to be formally correct we need to combine iteration with induction
View Full Document
Unlocking...