Solving Recurrence RelationsDegree of a Recurrence RelationLinear Recurrence RelationsHomogeneous Recurrence RelationsSlide 5Solving 2nd Order LHRRCCStep 1Step 2Step 3Step 4Step 5ExampleExercisesCSE 2813 Discrete StructuresSolving Recurrence RelationsSection 6.2CSE 2813 Discrete StructuresDegree of a Recurrence Relation•The degree of a recurrence relation is k if the sequence {an} is expressed in terms of the previous k terms: an c1an-1 + c2an-2 + … + ckan-kwhere c1, c2, …, ck are real numbers and ck 0•What is the degree of an 2an-1 + an-2 ?•What is the degree of an an-2 + 3an-3 ?•What is the degree of an 3an-4 ?CSE 2813 Discrete StructuresLinear Recurrence Relations•A recurrence relation is linear when an is a sum of multiples of the previous terms in the sequence•Is an an-1 + an-2 linear ?•Is an an-1 + a2n-2 linear ?CSE 2813 Discrete StructuresHomogeneous Recurrence Relations•A recurrence relation is homogeneous when an depends only on multiples of previous terms.•Is an an-1 + an-2 homogeneous ?•Is Pn (1.11)Pn-1 homogeneous ?•Is Hn 2Hn-1 + 1 homogeneous ?CSE 2813 Discrete StructuresSolving Recurrence Relations•Solving 1st Order Linear Homogeneous Recurrence Relations with Constant Coefficients (LHRRCC)–Derive the first few terms of the sequence using iteration–Notice the general pattern involved in the iteration step–Derive the general formula–Now test the general formula on some previously calculated (by iteration) termsCSE 2813 Discrete StructuresSolving 2nd Order LHRRCC•Form: an c1an-1 + c2an-2 with some constant values for a0 and a1•Assume that the solution is an rn, where r is a constant and r 0CSE 2813 Discrete StructuresStep 1•Solve the characteristic quadratic equation r2 – c1r – c2 = 0 to find the characteristic roots r1 and r22422112,1cccrCSE 2813 Discrete StructuresStep 2•Case I: The roots are not equal an = 1r1n + 2r2n•Case II: The roots are equal (r1=r2=r0) an = 1r0n + 2nr0nCSE 2813 Discrete StructuresStep 3•Apply the initial conditions to the equations derived in the previous step.–Case I: The roots are not equal a0 = 1r10 + 2r20 = 1 + 2 a1 = 1r11 + 2r21 = 1r1 + 2r2–Case II: The roots are equal a0 = 1r00 + 20r00 = 1 a1 = 1r01 + 21r01 = (1+2)r0CSE 2813 Discrete StructuresStep 4•Solve the appropriate pair of equations for 1 and 2.CSE 2813 Discrete StructuresStep 5•Substitute the values of 1, 2, and the root(s) into the appropriate equation in step 2 to find the explicit formula for an.CSE 2813 Discrete StructuresExample•Solve the recurrence relation: an 4an-1 4an-2where a0 a1 1•Solve the recurrence relation: an an-1 + 2an-2where a0 2 and a1 7CSE 2813 Discrete StructuresExercises•1,
View Full Document
Unlocking...