Recurrence Relations |
Examples
an = 7an-1 - 5an-2
is a recurrent relation valid for n 2. The elements in the sequence that are not related by the above formula are a0 and a1. Hence a0 and a1 can be determined by the initial conditions. Once the values of a0 and a1 are specified, the whole sequence {ai}i 0 is completely specified by the recurrence relation.
an = 3an-1 + 2an-2 | (*) |
a0 = 1, a1 = 2 . | (**) |
Solution
Recursively we use (*) repeatedly (''topdown'') to decrease
the indices involved until they all reach the initial ones. Hence
a4 | = | 3a3 + 2a2 | used (*) for n=4 |
= | 3(3a2 + 2a1) + 2a2 | used (*) for n=3 | |
= | 11 a2 + 6a1 | ||
= | 11 (3a1 + 2a0) + 6a1 | ||
= | 39a1 + 22a0 | ||
= | 39 2 + 22 1 = 100 . | used (**) |
a0 | = | 1 , | |
a1 | = | 2 , | |
a2 | = | 3a1 + 2a0 = 8 , | |
a3 | = | 3a2 + 2a1 = 28 , | used (*) for n=3 |
a4 | = | 3a3 + 2a2 = 100 . | used (*) for n=4 |
f(n) | = | n f(n-1), n , n 1 | |
f(0) | = | 1 | (initial condition) . |
Solution We first derive
f(n) | = | nf(n-1) | if n 1 |
= | n(n-1) f(n-2) | if n 2 | |
= | n(n-1)(n-2)f(n-3) | if n 3 | |
= | n! f(0) = n! . |
cman+m + cm-1an+m-1 + ... + c1an+1+c0an = g(n), n 0 | (***) |
Examples
ak+2 - 5ak+1 - 2ak = 3k+2, k 0 .
In terms of the notation in (***) we have in this case m=2 and
cm=c2=1, cm-1=c1=-5, cm-2=c0=-2, g(n)=3n+2 .
cman+m+ cm-1cn+m-1 + ... + c1 an+1 + c0an = g(n), n 0
with cmc0 0 is the following polynomial equation
cm m + cm-1m-1 + ... + c1 + c0 = 0 .
Examples
Note An alternative way to construct the characteristic equation: Since the highest index in the recurrence relation is n+1 while the lowest index is n-2, their difference (n+1)-(n-2)=3 must be the order m, i.e. m=3. Likewise the characteristic equation can also be obtained in following way.
Theorem If the characteristic equation of an m-th order homogeneous, linear, constant coefficient recurrence relation
cman+m + cm-1an+m-1 + ... + c1an+1+c0an = 0, cmc0 0, n 0
has m distinct roots 1, 2, , m, then
an = A1 1n + A22n + ... + Ammn
with arbitrary constants A1, , Am is the general solution of the recurrence relation.
Proof First we show an = Ai ni is a solution. For
this purpose we substitute the expression for an
into the recurrence relation and obtain
cman +m | + | + c1an+1 + c0a0 |
= | cm(A1 n+m1 + + Am mn+m) + + c1 (A1 1n+1 + + Am mn+1) | |
+ c0(A1 n1 + + Am nm) | ||
= | A1 (cm n+m1 + + c1 n+11 + c0 n1) + A2 (cm 2n+m + + c1 n+12 + c0 n2) | |
+ + Am(cm n+mm + + c1 mn+1 + c0 mn ) | ||
= | Ai in (cm im+ + c1 i + c0 ) = 0 . |
Aiik = ak, k=0, 1, ... , m-1
has a (unique) solution for A1, , Am, the expression an = Ai ni is indeed a general solution.
Note If the roots 1, , m are not distinct, i.e. there are repeated roots, then an = Ai ni is still a solution but is not a general solution. The general solution for such cases will be dealt with in the next lecture.
Example
an+2 - 5an+1 + 6an = 0 , n 0 .
Give also the particular solution satisfying a0 = 0 and a1=1.
Solution Since the associated characteristic equation is
2 - 5 + 6 = 0
and has 2 distinct roots 1
= 2 and 2 = 3, the
general solution for the recurrence relation, according to the theorem
earlier on, thus read an = A12n +
A23n, n 0,
where A1 and A2 are 2 arbitrary
constants. To find the particular solution, we need to determine
A1 and A2 explicitly by the
initial conditions a0 = 0 and a1 =
1. Hence we require
a0 = A120 + A230 = 0 |
a1 = A1 21 + A231 = 1 |
A1 + A2 = 0 |
2A1 + 3A2 = 1 |
Note It is often a good practice to check your answers, even if just partially. To check the above particular solution, we see
an+2 - 5an+1 + 6an | = | (-2n+2 + 3n+2) -5(-2n+1 + 3n+1) + 6 (-2n + 3n) |
= | -2n (22 - 5 2+6) + 3n (32 - 5 3 + 6) = 0 . |