文档介绍：Chapter 10 Recurrence Relations
Wen-Hsiang Lu (盧文祥)
Department puter Science and Information Engineering,
National Cheng Kung University
2005/06/06
1
10. Recurrence Relations
The First-Order Linear Recurrence Relation
The equation an+1 = 3an is a recurrence relation with constant coefficients. Since an+1 only depends on its immediate predecessor, the relation is said to be first order. The expression a0 = A, where A is a constant, is referred to as an initial condition.
The unique solution of the recurrence relation an+1 = dan, where n 0, d is a constant, and a0 = A, is given by an = Adn.
2
10. Recurrence Relations
The First-Order Linear Recurrence Relation
Example : Solve the recurrence relation an = 7an-1, where n 1 and a2 = 98.
an = a0(7n), a2 = 98 = a0(72) a0 = 2, an = 2(7n).
Example : A bank pay 6% annual interest on savings, compounding the interest monthly. If we deposit $1000, how much will this deposit be worth a year later?
pn+1 = ()pn, p0 = 1000 pn = p0()n
p12 = 1000()12 = $
3
10. Recurrence Relations
The First-Order Linear Recurrence Relation
Refer to examples , , , and .
Example : Let an count the number positions of n, we find that
an+1= 2an, n 1, a1= 1 an = 2n-1
4
10. Recurrence Relations
The First-Order Linear Recurrence Relation
The recurrence relation an+1- dan = 0 is called linear because each term appears to the first power.
Sometimes a nonlinear recurrence (., an+1- 3anan-1 = 0) relation can be transformed to a linear one by a suitable algebraic substitution.
Example : Find a12 if an+12 = 5an2 where an > 0 for n 0 and a0 = 2.
Let bn = an2. Then bn+1= 5bn (linear) for n 0 and b0 = 4 bn =
5
10. Recurrence Relations
Homogeneous and Nonhomogeneous
The general first-order linear recurrence relation with constant coefficients has the form an+1 + can = f(n).
f(n) = 0, the relation is called homogeneous.
Otherwise, it is called nonhomogeneous.