Discrete Structures ENGR 213
Christopher Newport University
Popular in Course
Popular in Engineering and Tech
This 17 page Class Notes was uploaded by Tony Davis on Monday October 5, 2015. The Class Notes belongs to ENGR 213 at Christopher Newport University taught by Dali Wang in Fall. Since its upload, it has received 6 views. For similar materials see /class/219482/engr-213-christopher-newport-university in Engineering and Tech at Christopher Newport University.
Reviews for Discrete Structures
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/05/15
Solving Recurrence Relations Section 62 of the Text Review nth degree polynomials have n roots an x an1x 391 alx a0 O If the coefficients are real then the roots are real or occur in complex conjugate pairs Recall the quadratic formula ax2 bx C 0 then xZ bim 2a Solving Recurrence Relations Review We assume you remember how to solve linear systems AX b where A is an n x n matrix Example Solving Recurrence Relations Statement of the Problem aga 9 agn1 a form or an express10n for a gm Example fn 3n lt gt f01fn 3fn1 Solving Recurrence Relations Form of Recurrence Equations Solving recurrence relations can be very difficult unless the recurrence equation has a special form gn n single variable the equation is linear sum of previous terms no transcendental functions of the aquot s o no products of the ai s constant coefficients the coefficients in the sum of the a s are constants independent of n Solving Recurrence Relations 5 Form of Recurrence Equations cont unless the recurrence equation has a special form degree k an is a function of only the previous k terms in the sequence homogeneous If we put all the a39s on one side of the equation and everything else on the right side then the right side is O OthenNise inhomogeneous or nonhomogeneous Solving Recurrence Relations Form of Recurrence Equations cont A recurrence relation an fan1 ank has degree k if the function f depends on the term ank and if it depends on no terms of lower index It is linear of degree k if it has the form an Clanl CZanZ Ckank Where each ck is a real function and ok 72 0 It is homogenous if gn 0 Solving Recurrence Relations Examples linear const homo degree coef geneous an 2 1 02an1 an 102an1 2n1 an 2 an1 aw am3 2n393 an 2 canm b 2 an nan1 n an2 an lan Z Solving Recurrence Relations Solving Recurrence Equations A linear mmogeneous currence of degree llt with Qnstant Qef cients kLiHoReCoCo is a reccurrence relation of the form an c1aa1 ckank where the c are all real and ckq O The solution is uniquely determined if k initial conditions a0ak1 are provided Solving Recurrence Relations Solution Procedure Equation kLiHoReCoCo an Clan1 CZaHZ o o o Ckank Steps 1 Put all ai39s on the left side of the equation everything else on the right If nonhomogeneous stop for now an c1an1 02am2 ckank O 2 Assume a solution of the form an bquot Substitute the solution into the equation factor out the lowest power of b and eliminate it b 0119 Czbn392 ckb 39k O bn39kbk clbk391 ck 0 Solving Recurrence Relations 10 Solution Procedure cont Steps 3 The remaining polynomial of degree k bk clbk 1 ck is called the characteristic polynomial The corresponding equation is called characteristic equa on Find its k roots r1 r2 rk 4 If the roots are distinct the general solution is an owl 0c2r2 ockrk Solving Recurrence Relations 11 Solution Procedure cont Steps 5 The coefficients a1 a2 ak are found by enforcing the initial conditions Solve the resulting linear system of equations a0 0L1r10 0L2r20 Ockrk0 a1 0L1r11 0L2r21 Ockrk1 ak l Ollrlk 391 ourzk 391 0Lkrkk 391 Solving Recurrence Relations 12 Examples Solving the recurrence equation an 3an1aO 4 Solution Step 1 Bring subscripted variables to one side an3an1 O Step 2 Substitute an bn and factor lowest power of b bn391b3 O or b3 O Step 3 Find the root of the characteristic equation r1 3 Solving Recurrence Relations 13 Examples cont Solution cont Step 4 Compute the general solution an c3n Step 5 Find the constants based on the initial conditions 210 C30 or c 4 Finally Produce the specific solution an 43 Solving Recurrence Relations 14 Examples Solving the recurrence equation an3a n2 a0 2 a1 2 1 Solving Recurrence Relations The Case of Degenerate Roots If a root r1 has multiplicity p then the solution corresponding the root is oc1 oc2n ocpnp391r1 For quadratic case if the characteristic equation r2 c1r 02 O has only 1 root r0 then an 01r0 aznro for all n20 for some constants a1 a2 Solving Recurrence Relations Examples Solving the recurrence equation an 2 6an1 9a n Z aOZalzl Solving Recurrence Relations