文档介绍：Computer Science and Information Engineering
National Chi Nan University
Combinatorial Mathematics
Dr. Justie Su-Tzu Juan
Chapter 10 Recurrence Relation
§ The Nonhomogeneous
Recurrence Relation
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 Nonhomogeneous Recurrence Relation
an + cn1an1 = f(n), n 1 (1)
an + cn1an1 + cn2an2 = f(n), n 1 (2)
1 0, cn2 0, f(n) 0.
A. 1 = 1 of (1): an an1 = f(n)
a1 = a0 + f(1)
a2 = a1 + f(2) = a0 + f(1) + f(2)
a3 = a2 + f(3) = a0 + f(1) + f(2) + f(3)
: n
a = a + f(i)
n 0 i1
2
Ex : an an1 = 3n , where n 1
a0 = 7 n n n
Sol. f(n) = 3n2 f(i) = 3i2 = 3i2 = 3n(n + 1)(2n + 1)/6 2
i1 i1 i1
an = 7 + (1/2)n(n + 1)(2n + 1)
(c) Spring 2007, Justie Su-Tzu Juan 2
§ The Nonhomogeneous Recurrence Relation
B. method of undetermined coefficient: (for certain function f(n))
(h)
 Let an the general solution of f(n) = 0 in (1) (or (2))
(p)
 Let an (particular solution) a solution of (1) (or (2))
(h) (p)
 an = an + an is the general solution of (1) (or (2))
n
Ex : an 3an1 = 5(7 ), n 1
a0 = 2
(h) (h) (h) n
Sol.  an 3an1 = 0  an = c(3 )
∵ f(n) = 5(7n)
(p) n n n1 n
Let an = A(7 )  A(7 ) 3A(7 ) = 5(7 ), n 1
 7A 3A = 5 7 = 35  4A = 35  A = 35/4
(p) n n+1
∴ an = (35/4) 7 = (5/4) 7
n n+1
 an = c(3 ) + (5/4) 7
∵ a0 = 2 = c + (35/4)  c = 27/4
n+1 n+3
∴ an = (5/4) 7 (1/4) 3 , n 0
(c) Spring 2007, Justie Su-Tzu Juan 3
§ The Nonhomogeneous Recurrence Relation
n
Ex : an 3an1 = 5(3 ), n 1
a0 = 2
Sol.
(h) n
 an = c(3 )
n (h)
∵ f(n) = 5(3 ) and an are not linearly independent
(p) n
∴ let an = B n(3 )
 B n(3n) 3B(n 1)(3n1) = 5(3n)
 Bn B(n 1) = 5
 B = 5
(p) n
∴ an = 5n 3
n n n
 an = c(3 ) + 5n 3 = (c + 5n) 3
a0 = 2 = c
n