1.
A
recurrence relation of degree k for a sequence {an}
is an equation
an = f(an-1, an-2, an-3, ..., an-k)
that defines an in terms of the k previous terms of
the sequence (1£. k £ n).
2.
A
solution to a recurrence relation is a sequence that satisfies the
recurrence relation.
3.
A
recurrence relation plus initial conditions produces a recursively
defined sequence.
4.
Example
The sequence an = 3n (that is, the sequence (0, 3,
6, 9 ...)) and the sequence an = 5 (that is, the sequence (5,
5, 5, 5 ...)) are both solutions to the recurrence relation an
= 2an-1 - an-2
5.
Example
The recurrence relation for compound interest at 9 percent is
Pn = 1.09Pn-1. The sequence {Pn}
defined by the explicit formula Pn = (1.09)nP0
satisfies (is a solution to) this recurrence relation.
6.
Example
The breeding rabbits problem. Each pair of rabbits produces another pair of
rabbits each month after they are 2 months old. The number on the island this
month equals the number last month plus the newborns (which equal the number of
rabbits 2 month ago). fn =fn-1 + fn-2
and f1 = 1, f2 = 1, producing the Fibonacci
sequence (1, 1, 2, 3, 5, 8,
).
7.
Example
The number of moves required to solve The Tower of Hanoi problem with n
disks, Hn, satisfies the recurrence relation Hn
= 2Hn-1 + 1 and the initial condition , H1 =
1. The solution to this recurrence relation (and initial condition) is Hn = 2n
1.
8.
Example
Find he number an of bit strings of length n that do
not contain two consecutive zeros. an must either end with a
1 (add 1 to one of the an-1 legal strings of length n-1)
or with a 0 (add 10 to one of the an-2 legal strings of
length n-2). a1 = 2, a2 = 3, and an
= an-1 + an-2.Note
that an = fn-2.
9.
Example
If a legal account number contains an even number of 0 digits, a1
= 9, and an = 9*an-1 + (10n-1
- an-1). (You can generate a legal account of
length n by appending 1 through 9 to a legal account of length n-1
or by appending a zero to an illegal account of length n-1.