From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Fri Apr 4 11:14:35 2008 Date: Fri, 4 Apr 2008 10:54:07 -0400 From: "William J. Rapaport" Subject: 191: General method for solving recurrence relations To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: 191: General method for solving recurrence relations ------------------------------------------------------------------------ The general algorithm for solving a recurrence relation (well, for solving a linear homogeneous recurrence relation with constant coefficients of degree 2) is: 0. Input the recurrence relation and initial conditions: a) initial conditions ("base case"): a0 = C0 (some constant) a1 = C1 (some constant) b) recurrence relation ("recursive case"): a_n = c1*a_(n-1) + c2*a_(n-2) ------------------------------------------------------------------------ 1. Find the characteristic equation of the recurrence relation: a) the char eqn is: r^2 - c1*r - c2 = 0 where "r" is a variable, & the c_i are the recurrence relation's coefficients ------------------------------------------------------------------------ 2. Solve the char eqn: a) Either factor it, or, when in doubt, use the quadratic formula: Any quadratic equation of the form: ax^2 + bx + c = 0 has two (not necessarily distinct) solutions: x = [-b +/- sqrt(b^2 - 4ac)]2a In the present case, the char eqn is a quad eqn in which a = 1, b = -c1, c = -c2, so the quad fmla is: r = [c1 +/- sqrt(c1^2 + 4*c2)]/2 b) This step outputs two solutions: r1, r2 ------------------------------------------------------------------------ 3. (Here, I will use the "@" sign instead of "alpha".) Find @1, @2 such that a_n = @1*r1^n + @2*r2^n, which (by Thm 1, p. 462), is the non-recursive "solution" to the recurrence relation. To do this, use the initial conditions: a) a0 = @1*r1^0 + @2*r2^0 = @1 + @2 (1) a1 = @1*r1^1 + @2*r2^1 = r1*@1 + r2*@2 (2) b) Then solve this pair of simultaneous equations in 2 unknowns. (I'll assume that you know how to do this.) ------------------------------------------------------------------------ 4. Summarize what you've just done by re-writing a_n in non-recursive form as: a_n = @1*r1^n + @2*r2^n ------------------------------------------------------------------------ 5. You can check your work by substituting this non-recursive formula into the recurrence relation. If you are correct, then the result should be the original non-recursive formula. ------------------------------------------------------------------------ In my next Listserv message, I'll apply this to solving a Fibonacci recurrence relation.