Second-Order Recurrence Relations: A Detailed Guide
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,
a
k
= Aa
k-1
+ Ba
k-2
for 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 (a
k-1
, a
k-2
).
–
Its linear a
k-1
, a
k-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.
•
a
k
= 3a
k-1
+ 2a
k-2
•
b
k
= b
k-1
+ b
k-2
+ b
k-3
•
d
k
= d
2
k-1
+ d
k-1
* d
k-2
•
e
k
= 2e
k-2
•
f
k
= 2f
k-1
+ 1
Distinct Roots
•
Lemma 8.3.1
–
Let A and B be real numbers. A recurrence relation
of the form a
k
= Aa
k-1
+ Ba
k-2
is satisfied by the
sequence 1, t, t
2
, t
3
, … , t
n
, … where t is non-zero
real number if, and only if, t satisfies the equation
t
2
– At – B = 0.
Characteristic Equation
•
Definition
–
Given a second-order linear homogenous
recurrence relation with constant coefficients:
a
k
= Aa
k-1
+ Ba
k-2
for all ints k≥2,
the characteristic equation of the relation is
t
2
– 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.
a
k
= a
k-1
+ 2a
k-2
–
Find all sequences that satisfy 1, t, t
2
, t
3
, … , t
n
, …
–
Solution
•
t
2
– t - 2 = 0
•
t
2
– t - 2 = (t – 2)(t + 1), thus the values of t = 2, -1
•
t can be: 1, 2, 2
2
, 2
3
, … , 2n OR 1, -1
2
, -1
3
, … -1
n
•
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 a
k
= Aa
k-1
+ Ba
k-2
for ints k≥2, but consider that the
characteristic equation t
2
– At – B = 0 has a single root.
•
By Lemma 8.3.1 one sequence that satisfies the relation is:
1, r, r
2
, r
3
, … r
n
, … however another is: 0, r, 2r
2
, 3r
3
, … , nr
n
•
To see this observe:
t
2
– At – B = (t – r)
2
= t
2
– 2rt – r
2
, A=2r B=-r
2
•
s
n
= nr
n
for all ints n≥0
•
As
k-1
+ Bs
k-2
= A(k -1)r
k-1
+ B(k -2)r
k-2
= 2r(k -1)r
k-1
+ -r
2
(k -2)r
k-2
= 2(k -1)r
k
-
(k -2)r
k
= (2k – 2 – k + 2) r
k
= kr
k
= s
k
Single Root
•
Lemma 8.3.4
–
Let A and B be real numbers and suppose the
characteristic eq t
2
– At – B = 0
has a single root r. Then the sequence 1, r
1
, r
2
, … ,
r
n
, … and 0, r, 2r
2
, … nr
n
, … both satisfy the
recurrence relation
a
k
= Aa
k-1
+ Ba
k-2
for all ints k≥2
Single Root
•
Theorem 8.3.5
–
Suppose a sequence satisfies a recurrence relation
a
k
= Aa
k-1
+ Ba
k-2
for some real numbers A and B with B≠0 and for all
ints k≥2. If the characteristic eq t
2
– At – B = 0
has a single (real) root r then the sequence a
0
, a
1
, a
2
,
… satisfies the explicit formula
a
n
= Cr
n
+ Dnr
n
where C and D are the real numbers whose values are
determined by the values of a
0
and any other known
value of the sequence.
Example
•
Suppose b
0
, b
1
, b
2
… satisfies the recurrence relation b
k
= 4b
k-1
– 4b
k-
2
for all ints k ≥ 2 with initial conditions b
0
= 1 and b
1
= 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 t
2
– 4t + 4 = 0 has a single
root r = 2 ( (t-2)(t-2) )
–
b
n
= C 2
n
+ Dn2
n
–
to find C and D use initial conditions
•
b
0
= 1 = C 2
0
+D(0)2
0
=>
C = 1
•
b
1
= 3 = C 2
1
+D(1)2
1
=>
2C + 2D = 3 (sub C = 1 from above)
•
3 = 2(1) + 2D => D = ½
–
Hence, b
n
= 2
n
+ ½ n2
n
for all ints n≥2
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.
E N D
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
