文档介绍：Computer Science and Information Engineering
National Chi Nan University
Combinatorial Mathematics
Dr. Justie Su-Tzu Juan
Chapter 10 Recurrence Relations
§ The Second-Order Linear
Homogeneous Recurrence Relation with
Constant Coefficients
Slides for a Course Based on the Text
Discrete & Combinatorial Mathematics (5th Edition)
by Ralph P. Grimaldi
(c) Spring 2007, Justie Su-Tzu Juan 1
§ The Second-Order Linear Homogeneous
Recurrence Relation with Constant Coefficients
+
Def: Let k Z , cn, cn1, cn2, …, cnk R {0}. an is a discrete function for
n 0:
1. cnan + cn1an1 + cn2an2 + …+ cnkank = f(n), n k,
is a linear recurrence relation (with constant coefficients) of order k.
2. if f(n) = 0 for all n 0; the relation is called homogeneous;
otherwise, it is nonhomogeneous.
∴ k = 2  cnan + cn1an1 + cn2an2 = 0, n 2
homogeneous n
seek solution: an = cr , c 0, r 0.
0
n 2 n11 n2
代入 cn cr + cn1 cr + cn2 cr = 0
2
 cn r + cn1 r + cn2 = 0
(c) Spring 2007, Justie Su-Tzu Juan 2
§ The Second-Order Linear Homogeneous
Recurrence Relation with Constant Coefficients
2
Def: 3. cn r + cn1 r + cn2 = 0 is called the characteristic function.
4. The roots r1, r2 of characteristic function are called characteristic
roots.
 3 case: (A) Distinct Real Roots
(B) (Conjugate) Complex Roots
(C) Repeated Real Roots
(c) Spring 2007, Justie Su-Tzu Juan 3
§ The Second-Order Linear Homogeneous
Recurrence Relation with Constant Coefficients
Case (A): Distinct Real Roots
Ex : an + an1 6an2 = 0, where n 2,
a0 = 1, a1 = 8.
Sol.
n
Let an = cr with c 0, r 0
 r2 + r 6 = 0
 r = 2, 3
∵k R . 2n = k(3)n for all n. (linear independent solutions)
n n
Let an = c1(2 ) + c2(3) , c1, c2 R. (general solution)
0 0
∵ a0 = 1 = c1 2 + c2 (3) = c1 + c2
a1 = 8 = c1 2 + c2 (3) = 2c1 3c2
. 1 = c + c 2 = 2c + 2c c = 1
1 2  1 2  1