Recurrence Relations

Recurrence Relations

A recurrence relation for a given sequence {ai}i m is a formula that relates each ak to some of its predecessors. The first few elements in the sequence that can not be related to each other by the recurrence relation are often determined by the initial conditions.

Examples

  1. For sequence {ai}i , the following formula

    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.

  2. Let a sequence {ai}i be determined by the recurrence relation
    an = 3an-1 + 2an-2 (*)
    and the initial conditions
    a0 = 1, a1 = 2 . (**)
    Calculate a4 recursively first. Then calculate a4 again iteratively.

    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 (**)
    Iterately we use (*) repeatedly (''building-up'') to derive more and more known elements until the desired index is reached. Hence
    a0 = 1 ,
    a1 = 2 ,
    a2 = 3a1 + 2a0 = 8 ,
    a3 = 3a2 + 2a1 = 28 , used (*) for n=3
    a4 = 3a3 + 2a2 = 100 . used (*) for n=4

  3. Let f(n) for n be given by the recurrence relation
    f(n) = n f(n-1), n , n 1
    f(0) = 1 (initial condition) .
    Find the solution f(n).

    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! .
    Then we can show inductively f(n) = n! for n 0.

Basic Concepts Related to Recurrence Relations

An m-th order linear constant coefficient recurrence relation on a sequence {an}n 0 is a recurrence relation which can be written in the form
cman+m + cm-1an+m-1 + ... + c1an+1+c0an = g(n),   n 0 (***)
where c1, , cm are constants, c0cm 0, and g(n) is a function of n. If furthermore g(n) = 0 for all n, then the relation is said to be homogeneous.

Examples

  1. an = 5an-1 + 2an-2 + 3n,   n 2, is a 2nd order linear constant coefficient recurrence relation and is nonhomogeneous. This is because we can equivalently rewrite it as

    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 .

  2. Bn+2 = sin (Bn+1),   n -1, is not a linear recurrence relation because sin(Bn+1) is not a linear function of the dependent function Bn+1.
  3. an+1 = nan,   n 0, is not a constant coefficient recurrence relation, though it is linear and homogeneous.
  4. f(n+1) = 3f(n-5) + 4 f(n-2),   n 5, is a homogeneous, 6th order, linear, constant coefficient recurrence relation. Observe that the difference of the highest index (n+1) and the lowest index (n-2) is exactly the order 6 of the recurrence relation.
  5. an+1 = ran with constant r and n 0 induces a geometric sequence {an}n 0 with an = ran-1 = r(ran-2) =r2an-2 = = rna0, i.e. an = rna0 as its solution.
The characteristic equation of linear constant coefficient recurrence relation

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

  1. Recurrence relation an+2 + 3an+1 + 2an = 0, n 0, has the characteristic equation 2 + 3 + 2 = 0.
  2. Recurrence relation f(n+1) = 3f(n-2) + n2 + 5, n 2 has the characteristic equation 3 - 3 = 0 because the recurrence relation can be written via n = k+2 as f(k+3) - 3f(k) = (k+2)2 + 5. In fact we have in this case cm c3=1, c2=0, c1=0 and c0=-3 in (***), and thus the characteristic equation c3 3+c2 2+c1 +c0=0 becomes simply 3-3=0.

    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.

    (i)
    Remove the nonhomogeneous terms g(n). This way the recurrence relation f(n+1) = 3f(n-2) + n2 + 5 becomes the reduced recurrence relation f(n+1) = 3f(n-2).
    (ii)
    Find the lowest index L. Here we thus have L=n-2.
    (iii)
    For each term in the reduced recurrence relation, if its index is K then replace the term by K-L. For the term f(n+1) we see K=n+1 hence K-L=(n+1)-(n-2)=3. Hence f(n+1) is to be replaced by 3. Likewise for the term f(n-2) on the r.h.s. we see K=n-2 hence K-L=0, implying that the term f(n-2) is to be replaced by 0 which is simply 1. This way the reduced recurrence relation is finally replaced into the characteristic equation 3=1.

Simplest Case of General Solutions

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 .
Hence an = Ai in is a solution. Since the solution involves m arbitrary constants A1, , Am, it is in fact a general solution. Alternatively we can also argue that for any initial values of a0, , am-1, since the linear system of m equations

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

  1. Find the general solution of

    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
    i.e.
    A1 + A2 = 0
    2A1 + 3A2 = 1
    The solution of the above equations are found to be A1 = -1 and A2 = 1. Thus the particular solution is an = -2n + 3n for n 0.

    Note It is often a good practice to check your answers, even if just partially. To check the above particular solution, we see

    a0 = -20 + 30 = 0
    a1 = - 21 + 31 = 1
    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 .
    i.e. all conditions satisfied.