V Adamchik 1 Recursions Victor Adamchik Fall of 2005 Plan 1 Solving Linear Recurrences with Constant Coefficients 1 1 Iterations 1 2 Characteristic equation 1 3 General solution 1 4 Higher order equations 1 5 Multiple roots Solving Second Order Recurrences Iteration Let us apply the method of iteration to a second order liner recurrence equation As an example we choose the Fibonacci sequence Iterating it ones we obtain an an 1 an 2 an 1 an 2 an 3 an 2 an 3 an 4 an an 2 2 an 3 an 4 Iterating it twice an an 2 2 an 3 an 4 an 2 an 3 an 4 an 3 an 4 an 5 an 4 an 5 an 6 an an 3 3 an 4 3 an 5 an 6 We see that iteration does not work in this case the terms in the right hand side do not cancel and therefore the pattern does not emerge V Adamchik 21 127 Concepts of Mathematics Characteristic Equation In this section we will develop a new method of solving linear recurrences As a demo example we choose the Fibonacci numbers Fn Fn Fn 1 2 Let us observe that the Fibonacci sequence is growing Fn Therefore if we formally replace Fn 2 Fn 2 Fn 1 term by Fn 1 we get Fn Fn 1 2 Fn 2 Fn Fn 2 2 Fn Fn 2 1 On the other hand 1 Fn Therefore 2 Fn Fn 2 2 Fn 1 We introduce two new sequences bn 2 bn 1 cn 2 cn 2 cn Fn such that bn Both equations can be easily solved by iteration where and bn 2n 1 cn 2n 2 are some constants Thus we proved that 2n 2 2n Fn 1 What do we learn from this We form an educated guess that the Fibonacci equation has an exponential solution n Fn where is to be determined To find we plug this into the original equation Fn to obtain Fn 1 Fn 2 V Adamchik 3 n n 1 n 2 This leads a polynomial equation in n n 2 n 1 n 2 0 2 1 0 2 1 0 The last equation is called a characteristic equation The equation has two roots 5 1 1 2 5 1 2 2 Therefore 1 n 5 1 and 2 5 n 2 are solutions to the Fibonacci recurrence General Solution Let 1 n and 2 n be two solutions Then their linear combination an c1 1 n c2 2 n where c1 and c2 are arbitrary constants is also a solution Such solution is called a general solution We prove that a general solution is a solution by substitution an into the Fibonacci equation an an an 1 0 2 We obtain c1 1 n c2 2 n c1 1 n 1 c2 2 n 1 c1 1 n 2 c2 2 n 2 Collect terms by c1 and c2 yeilds c1 1 n 1 n 1 1 n 2 c2 2 n 2 n 1 2 n 2 Each term is zero since 1 and 2 are roots of the characteristic equation For the Fibonacci sequence the general solution is an c1 1 5 2 n c2 1 5 2 n V Adamchik 21 127 Concepts of Mathematics How do you find c1 and c2 We find them from the initail conditions For the Fibonacci sequence they are a0 0 a1 1 This leads to a system of two equations a0 c1 a1 1 c1 0 1 c2 1 2 c2 0 0 1 1 2 or c1 1 2 c1 c2 0 5 c2 1 2 5 1 The system can be easily solved We get 1 c1 5 1 c2 5 Hence Fn 1 1 n 5 2 5 1 1 5 n 2 5 In terms of the golden ratio n Fn n 1 5 Based on a closed form solution it s easy to prove lim n Fn 1 Fn Example We solve the following recurrence an 3 an a0 n Assume the solution in the form an The characteristic equation 1 4 an 0 a1 2 1 and substitute it to the equation to obtain n 3 n 1 n 2 2 3 4 4 n 2 0 V Adamchik 5 2 3 4 0 has two roots 1 and 1 4 2 The general solution is an c1 n 1 c2 4n We find c1 and c2 from initial conditions This gives us the following system a0 c1 c1 a1 c2 0 4 c2 1 Its solution 1 c2 5 c1 1 5 Finally the solution to the original recurrence is 1 5 an 1 5 n 1 4n Higher order equations The method of the charcteristic equation works for any order linear recurrence equation with constant coefficients The latter means that coefficients by all ak terms in the equation are free of n The following are equations with constant coefficients an an 1 an 2 an 1 1 an 2 an 1 3 These are not equations with constant coefficients n an an n an an 1 2 an 1 1 1 n 1 an Let us consider the following equation an a1 an 2 an 2 0 a2 3 a3 9 2 2 0 The characteristic equation 3 has three roots 2 3 2 V Adamchik 21 127 Concepts of Mathematics 1 1 1 2 3 2 The general solution an c1 1 n c2 1n c3 2n We find unknown coefficients from the system a0 a0 a1 c1 c2 c3 0 c1 c2 2 c3 3 c1 c2 4 c3 9 Therefore the solution is 3 2n an 1 Multiple roots Consider the following example 2 an an a0 an 1 1 a1 2 2 The characteristic equation 2 2 1 0 has two identical roots 1 2 1 The first solution is 1n But what is the second solution Generally what would be the solution of the recurrence if all or few roots of the characteristic equation are the same To get a notion of the second solution we consider a new equation bn 2 bn b0 It s easy to see that if tion for bn sequence is 1 1 b1 bn 2 2 0 then the sequence bn approaches an The characteristic equa2 It has two roots 1 2 1 0 V Adamchik 7 1 1 1 2 Therefore a general solution is c1 1n bn n 1 c2 where c1 and c2 are arbitrary Let us choose them in the special form 1 c1 Now consider a general solution when lim 0 1 n 1 lim 1 c2 0 1n 1n n 1 n 1 0 This is the second solution for an sequence Then the general solution is an c1 a0 1 a1 2 c1 1 c2 1 c2 n Taking into account initial conditions we find Hence an 1 n n
View Full Document
Unlocking...