Understanding Second-Order Recurrence Relations: A Detailed Guide
Explore the concept of second-order linear homogeneous recurrence relations with constant coefficients through definitions, examples, and the Distinct Roots Lemma. Learn about characteristic equations and how to find solutions to recurrence problems. Delve into the Single Root Case and understand how to identify sequences satisfying the relation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
Presentation Transcript
Chapter 8 Recursion
8.3 More Recurrence
Second-Order Recurrence Definition A second-order linear homogeneous recurrence relation with constant coefficients is a recurrence relation of the form, ak= Aak-1+ Bak-2for all ints k some fixed int, where A and B are fixed real numbers and B 0. This is called a second order because expression is based on the previous two terms (ak-1, ak-2). Its linear ak-1, ak-2 are separate terms of the first order. Homogenous because are terms are of the same order. Constant coefficient b/c A and B are fixed real numbers that do not depend on k.
Example State whether each is a second-order linear homogenous recurrence relation. ak= 3ak-1 + 2ak-2 bk= bk-1 + bk-2 + bk-3 dk= d2k-1 + dk-1 * dk-2 ek= 2ek-2 fk= 2f k-1 + 1
Distinct Roots Lemma 8.3.1 Let A and B be real numbers. A recurrence relation of the form ak= Aak-1+ Bak-2is satisfied by the sequence 1, t, t2, t3, , tn, where t is non-zero real number if, and only if, t satisfies the equation t2 At B = 0.
Characteristic Equation Definition Given a second-order linear homogenous recurrence relation with constant coefficients: ak= Aak-1+ Bak-2for all ints k 2, the characteristic equation of the relation is t2 At B = 0
Example Use characteristic eq to find solutions to a recurrence problem. Consider recurrence relation where kth term of a sequence equals the sum of the (k-1)st term plus twice the (k-2) term. ak= ak-1+ 2ak-2 Find all sequences that satisfy 1, t, t2, t3, , tn, Solution t2 t - 2 = 0 t2 t - 2 = (t 2)(t + 1), thus the values of t = 2, -1 t can be: 1, 2, 22, 23, , 2n OR 1, -12, -13, -1n This example demonstrates how to find two distinct sequences that satisfy a given second-order homogenous recurrence relation with constant coefficients.
Single Root Case Consider ak= Aak-1+ Bak-2for ints k 2, but consider that the characteristic equation t2 At B = 0 has a single root. By Lemma 8.3.1 one sequence that satisfies the relation is: 1, r, r2, r3, rn, however another is: 0, r, 2r2, 3r3, , nrn To see this observe: t2 At B = (t r)2= t2 2rt r2, A=2r B=-r2 sn= nrnfor all ints n 0 Ask-1+ Bsk-2= A(k -1)rk-1 + B(k -2)rk-2 = 2r(k -1)rk-1 + -r2 (k -2)rk-2 = 2(k -1)rk -(k -2)rk = (2k 2 k + 2) rk = krk= sk
Single Root Lemma 8.3.4 Let A and B be real numbers and suppose the characteristic eq t2 At B = 0 has a single root r. Then the sequence 1, r1, r2, , rn, and 0, r, 2r2, nrn, both satisfy the recurrence relation ak= Aak-1+ Bak-2for all ints k 2
Single Root Theorem 8.3.5 Suppose a sequence satisfies a recurrence relation ak= Aak-1+ Bak-2 for some real numbers A and B with B 0 and for all ints k 2. If the characteristic eq t2 At B = 0 has a single (real) root r then the sequence a0, a1, a2, satisfies the explicit formula an= Crn+ Dnrn where C and D are the real numbers whose values are determined by the values of a0and any other known value of the sequence.
Example Suppose b0, b1, b2 satisfies the recurrence relation bk= 4bk-1 4bk- 2for all ints k 2 with initial conditions b0= 1 and b1= 3. Find an explicit formula for the sequence. Solution sequences is of second-order linear homogenous recurrence relation with constant coefficients (A=4 and B=-4). The single-root condition is also met because the characteristic equation t2 4t + 4 = 0 has a single root r = 2 ( (t-2)(t-2) ) bn= C 2n+ Dn2n to find C and D use initial conditions b0= 1 = C 20+D(0)20 => C = 1 b1= 3 = C 21+D(1)21 =>2C + 2D = 3 (sub C = 1 from above) 3 = 2(1) + 2D => D = Hence, bn= 2n+ n2n for all ints n 2
