Javascript required
Skip to content Skip to sidebar Skip to footer
Home / Finding Particular Solution of Nonhomogeneous Recurrence Relation

Finding Particular Solution of Nonhomogeneous Recurrence Relation

Basics of Linear Nonhomogeneous Recurrence Relations

Connection between Homogeneous and Nonhomogeneous Problems

The solutions of linear nonhomogeneous recurrence relations are closely related to those of the corresponding homogeneous equations, as can be easily seen from the following.

Theorem Consider the following linear constant coefficient recurrence relation and its corresponding homogeneous form

cman+m+ + c1an+1+c0an = 0 . (**)

(i)
If vn and wn are two solutions of the nonhomogeneous equation (*) then
is a solution of the homogeneous equation (**).
(ii)
If un is the general solution of the homogeneous equation (**), and vn is any particular solution of the nonhomogeneous equation (*), then

an=un+vn ,   n 0

is the general solution of the nonhomogeneous equation (*).

Proof

(i)
The result is obvious from the following observation
(ii)
For an=un+vn , we have
i.e. an satisfies the nonhomogeneous recurrence relation (*). Since the general solution un of the homogeneous problem has m arbitrary constants thus so is an=un+vn . Hence an is the general solution of (*). More precisely, for any solution wn of (*), since (i) asserts n=wn-vn satisfies (**), n will just be a special case of the general solution un of (**). Hence wn= n+vn is included in the solution an=un+vn . Therefore an=un+vn is the general solution of the nonhomogeneous problem (*).

Examples of the First Glance

In the following, we'll give a few simple examples for finding particular solutions for nonhomogeneous problems. The arguments will be intuitive and some underneath subtleties are thus deliberately hidden at this stage to keep the main idea simple. Therefore the readers are urged not to make simplistic conclusion or generalisation based on the possible incomplete arguments in these examples, until you have read thoroughly the rest of the subject in the next lecture.

Examples

  1. Find a particular solution of an+2-5an=2 3n for n 0.

    Solution As the r.h.s. is 2 3n , we try the special solution in the form of an=C3n , with the constant C to be determined. The substitution of an=C3n into the recurrence relation thus gives

    i.e. 4C=2 or C=1/2. Hence an= (3n)/2 for n 0 is a particular solution.

  2. Find a particular solution of fn+1-2fn+3fn-4=6n, n 4.

    Solution As the r.h.s. is 6n, we try the similar form
    with constants A and B to be determined. Hence fn be a solution requires

    6n = fn+1 - 2fn + 3fn - 4
    = (A(n+1)+B) - 2(An+B) + 3(A(n-4)+B)
    = 2An + (2B-11A)
    i.e.
    which imples A = B = 33/2 .

    Therefore our particular solution is fn=3n + 33/2.

  3. Find the particular solution of

    an+3-7an+2+16an+1-12an=4nn

    with

    a0=-2 ,   a1 =0 ,   a2=5 .

    Solution We first find the general solution un for the corresponding homogeneous problem. Then we look for a particular solution vn for the nonhomogeneous problem without concerning ourselves with the initial conditions. Once these two are done, we obtain the general solution an=un+vn for the nonhomogeneous recurrence relation, and we just need to use the initial conditions to determine the arbitrary constants in the general solution an so as to derive the final particular solution of our interest.

    (a)
    The associated characteristic equation
    can be shown to admit the following roots
    We can easily verify this by first guessing 1 =3 is a root and then factorising 3-7 2+16 - 12 into ( -3)( 2 -4 +4) to find the remaining roots. If you are concerned that you might not be able to guess a first root like 1 in similar circumstances, then you can leave your worry behind because we won't expect you to make such a guess.

    The general solutions for the corresponding homogeneous problem thus reads

    un=A3n+(B+C n)2n ,   n 0 .

    That is, un solves an+3-7an+2+16an+1-12an=0.

    (b)
    Since the r.h.s. of the nonhomogeneous recurrence relation is 4n n, which fits into the description of 4n (1st order polynomial in n), we'll try a particular solution in a similar form, i.e.
    The substitution of vn into the original recurrence relation then gives
    i.e.
    n = 64(Dn+3D+E)-112(Dn+2D+E)
    + 64(Dn+D+E)-12(Dn+E)
    = 4Dn+4E+32D .
    Hence we have

    4D=1 ,   4E+32D=0 D=1/4 ,   E=-2

    and consequently vn=4n(n/4 - 2).
    (c)
    The general solution for the nonhomogeneous problem is then given by an=un+vn , i.e.

    an =4n(n/4 - 2) + A3n+(B+Cn)2n ,   n 0 .

    (d)
    We now determine A, B, C by the initial conditions and the use of the solution expression in (b)
    Initial Conditions Induced Equations Solutions
    A+B-2 = -2
    3A+2B+2C-24 = 5
    9A+4B+8C = 29
    Finally the particular solution satisfying both the nonhomogeneous recurrence relations and the initial conditions is given by

    an=4n(n/4 - 2) + 3n + (3n-1)2n ,   n 0 .

Note
1.
In all the examples in this lecture, it is easy to verify that the g(n) function in (*) is in the form of
where is not a root of the associated characteristic equation. If this were not the case, we would have to use different forms to try for the particular solutions. These will be the topics of the next lecture.
2.
If g(n)= n 1 n+ n 2(3n2+1), for instance, with 1 and 2 neither being a root of the characteristic equation, then the particular solution should be tried in the form
3.
If g(n) = cos ( n) n, for another instance, then we can treat it as

in which 1=ei and 2=e-i . Alternatively, we could try the particular solution in the form

Finding Particular Solution of Nonhomogeneous Recurrence Relation

Source: https://staff.cdms.westernsydney.edu.au/cgi-bin/cgiwrap/zhuhan/dmath/dm_readall.cgi?page=23