Solutions of Linear Nonhomogeneous Recurrence Relations

A Case for Thought

We already mentioned that finding a particular solution for a nonhomogeneous problem can be more involved than those exemplified in the previous lecture. Let us first highlight our point with the following example.

Example

  1. Solve an+2+an+1-6an=2n for n 0.

    Solution First we observe that the homogeneous problem
    un+2 + un+1 -6un=0
    has the general solution un=A 2n +B(-3)n for n 0 because the associated characteristic equation 2+ -6 =0 has 2 distinct roots 1=2 and 2=-3. Since the r.h.s. of the nonhomogeneous recurrence relation is 2n, if we formally follow the strategy in the previous lecture we would try vn=C2n for a particular solution. But there is a difficulty: C2n fits into the format of un which is a solution of the homogeneous problem. In other words it can't be a particular solution of the nonhomogeneous problem. This is really because ''2'' happens to be one of the 2 roots 1 and 2. However, we suspect that a particular solution would still have to have 2n as a factor, so we try vn=Cn2n. Substituting it to vn+2+vn+1 -6vn=2n, we obtain
    C(n+2)2n+2+C(n+1)2n+1-6Cn2n = 2n ,
    i.e. 10C2n=2n or C=1/10. Hence a particular solution is vn=(n/10)2n and the general solution of our nonhomogeneous recurrence relation is
    an=A2n+B(-3)n + 2n ,   n 0 .

In general, it is important that a correct form, often termed ansatz in physics, for a particular solution is used before we fix up the unknown constants in the solution ansatz. The choice of the form of a particular solution, covering the cases in this current lecture as well as the previous one, can be summarized below.

Method of Undertermined Coefficients

Consider a linear, constant coefficient recurrence relation of the form
cman+m+ + c1an+1+c0an=g(n) ,   c0cm 0 ,   n 0. (*)
Suppose function g(n), the nonhomogeneous part of the recurrence relation, is of the following form
g(n)= n(b0+ b1n + + bknk ) , (**)
where k , , b0, , bk are constants, and is a root of multiplicity M of the associated characteristic equation
cm m + + c1 +c0 =0 .
Then a particular solution vn of (*) should be sought in the form
vn = Bini n nM
= n ( B0 + B1n + + Bk-1nk-1 + Bk nk ) nM , (***)
where constants B0, , Bk are to be determined from the requirement that an =vn should satisfy the recurrence relation (*). Obviously the vn in (***) is composed of two parts: one is the n(B0+B1n+ +Bknk) which is of the same form of g(n) in (**), the other is the nM which is a necessary adjustment for the case when , appearing in g(n) in (**), is also a root (of multiplicity M) of the characteristic equation of the associated homogeneous recurrence relation.

Note

1.
If is not a root of the characteristic equation then just choose M=0, implying alternatively that is a ''root'' of 0 multiplicity.
2.
We can also try = . If we rewrite as , then the 1st part is essentially (***) while the 2nd part is just a solution of the homogeneous problem. It is however obvious that vn in (***) is simpler .
3.
We briefly hint why vn is chosen in the form of (***). Let , f( ) and Ps( ) be defined in the same way as we did in the derivation hints of the theorem in the lecture just before the previous one, and we'll also make use of some intermediate results there. Recall that (*) can be written as f( )an = g(n) and (**) implies g(n) Pk( ).
(i)
If f( ) 0, then f( ) Pk( ) Pk( ). Hence if we try vn = (B0 +B1n+ + Bknk) n Pk( ), then we can derive a set of exactly (k+1) linear equations in B0, , Bk, which can be used to determine these Bi's.
(ii)
If is a root of f( )=0 with multiplicity M 1, then
f( )PM-1( ) { 0 } ,   f( )PM+k( ) Pk( ) .
Hence if we try vn =nM(B0+ + Bknk) n PM+k( ), we'll again have a set of exactly (k+1) linear equations as the coefficients of the terms n, nn, , nnk. The (k+1) constants B0, , Bk can thus be determined from these linear equations.

Examples

  1. Find the general solution of f(n+2)-6f(n+1)+9f(n)=5 3n,   n 0.

    Solution Let f(n)=un+vn, with un being the general solution of the homogeneous problem and vn a particular solution.

    (a)
    Find un: The associated characteristic equation 2 -6 + 9 =0 has a repeated root =3 with multiplicity 2. Hence the general solution of the homogeneous problem
    un+2-6un+1+9un=0 ,   n 0
    is un = (A+Bn)3n.
    (b)
    Find vn: Since the r.h.s. of the recurrence relation, the nonhomogeneous part, is 5 3n and 3 is a root of multiplicity 2 of the characteristic equation (i.e. =3, k=0, M=2), we try due to (***) vn =B0 n nM Cn23n: we just need to observe that C3n is of the form 5 3n and that the extra factor n2 is due to =3 being a double root of the characteristic equation. Thus
    5 3n = vn+2-6vn+1+9vn
    = C(n+2)23n+2-6C(n+1)23n+1+9Cn23n
    = 18C3n .
    Hence C=5/18 and vn =(5/18)n23n. Therefore our general solution reads
    f(n) = A + Bn + n2 3n ,   n 0 .
  2. Find the particular solution of
    an+4-5an+3+9an+2-7an+1 +2an=3 , n 0
    satisfying the initial conditions a0 = 2, a1 = -1/2, a2 = -5, a3 = -31/2 .

    Solution We first find the general solution un for the homogeneous problem. We then find a particular solution vn for the nonhomogeneous problem without considering the initial conditions. Then an=un+vn would be the general solution of the nonhomogeneous problem. We finally make use of the initial conditions to determine the arbitrary constants in the general solution so as to arrive at our required particular solution.

    (a)
    Find un: Since the associated characteristic equation
    4-5 3 +9 2 -7 + 2 =0
    has the sum of all the coefficients being zero, i.e. 1-5+9-7+2=0, it must have a root =1. After factorising out ( -1) via 4-5 3+9 2-7 + 2 = ( -1)( 3-4 2+5 -2), the rest of the roots will come from 3-4 2+5 -2 =0. Notice that 3-4 2+5 -2=0 can again be factorised by a factor ( -1) because 1-4+5-2=0. This way we can derive in the end that the roots are
    1 =1 with multiplicity m1=3 , and
    2=2 with multiplicity m2=1 .
    Thus the general solutions for the homogeneous problem is
    un = (A+Bn+Cn2)1n+D2n ,
    or simply un=A+Bn+Cn2+D2n because 1n 1.
    (b)
    Find vn: Notice that the nonhomogeneous part is a constant 3 which can be written as 3 1n when cast into the form of (**), and that 1 is in fact a root of multiplicity 3. In other words, we have in (***) =1, k=0 and M=3. Hence we try a particular solution vn=En3 1n =En3. The substitution of vn into the nonhomogeneous recurrence equations then gives, using a formula in the subsection Binomial Expansions in the Preliminary Mathematics at the beginning of these notes,
    3 = vn+4-5vn+3+9vn+2-7vn+1+2vn
    = E(n+4)3-5E(n+3)3+9E(n+2)3-7E(n+1)3+2En3
    = E(n3 + 3n2 4+3n 42+43) -5E(n3 + 3n2 3+3n 32+33)
      + 9E(n3 + 3n2 2+3n 22+23) -7E(n3 + 3n2 1+3n 12+13) + 2En3
    = -6E ,
    i.e. E= -1/2. Hence vn= -n3/2.

    Note Should you find it very tedious to perform the expansions in the above, you could just substitute, say, n=0 into
    3 = E(n+4)3-5E(n+3)3+9E(n+2)3-7E(n+1)3+2En3
    to obtain readily 3=E43-5E33+9E23-7E=-6E. Incidentally you don't have to substitute n=0; you can in fact substitute any value for n because the equation is valid for all n. Obviously this alternative technique also applys even if there are more than 1 unknowns in the equation; we just need to substitute sufficiently many distinct values for n to collect enough equations to determine the unknowns. The drawback of this technique is that you have to make sure that the form you have proposed for vn is absolutely correct through the use of the proper theory, otherwise an error in the form for vn will go undetected in this alternative approach.

    (c)
    The general solution of the nonhomogenous problem thus read
    an = un + vn = A + Bn + Cn2 + D2n - n3/2.
    (d)
    We now ask the solution in (c) to comply with the initial conditions.
    Initial Conditions Induced Equations Solutions
    a0 = 2
    a1 = -1/2
    a2 = -5
    a3 = -31/2
    A+D = 2
    A+B+C+2D = 0
    A+2B+4C+4D = -1
    A+3B+9C+8D = -2
    A = 3
    B = -2
    C = 1
    D = -1
    Hence our required particular solution takes the following final form
    an = 3 - 2n + n2 - n3/2 - 2n,   n 0 .
  3. Find the general solution of an+1-an=n2n+1 for n 0.

    Solution

    (a)
    The general solution for homogeneous problem is un=A because the only root of the characteristic equation is 1=1.
    (b)
    Since n2n+1 = 2n n +1n is of the form 1n(b1n+b0)+ n2 c0 and 2=1 is a simple root of the characteristic equation, we try the similar form vn = 2n(B+Cn) + Dn for a particular solution. Substiting vn into the recurrence relation, we have
    n2n+1 = vn+1-vn = 2n+1(B+C(n+1)) + D(n+1) - 2n(B+Cn) - Dn
    = 2n(Cn+B+2C) + D ,
    i.e.
    2n ( (C-1)n + (B+2C) ) + (D-1) = 0 .
    In order the above equation be identically 0 for all n 0, we require all its coefficients to be 0, i.e.
    C-1=0 ,   B+2C=0 ,   D-1=0 .
    Hence B=-2, C=1 and D=1 and the particular solution vn =2n(n-2)+n.
    (c)
    The general solution is un+vn and thus reads
    an = 2n(n-2)+n+A , n 0 .
  4. Let m and S(n)= im for n . Convert the problem of finding S(n) to a problem of solving a recurrence relation.

    Solution We first observe
    S(n+1)= (n+1)m + im = S(n) + (n+1)m .
    Since the general solution will contain just 1 arbitrary constant, 1 initial condition should suffice. Hence S(n) is the solution of
    S(n+1)-S(n) = (n+1)m,     n
    S(0) = 0 .

Note A similar procedure for solving linear, constant coefficient nonhomogeneous recurrence relations can be found in the book by Stephen B Maurer et al,   Discrete Algorithmic Mathematics, Addison-Wesley, 1991.