CHAPTER 4

RECURRENCE RELATIONS
2.1. Introduction
Recursion involves recursive definition of an algorithm, a set or a sequence in terms of itself.
Recurrence relations are the discrete counterparts to the continuous ideas of the ordinary
differential equations. Recurrence relations are also called difference equations or recurrence
equations.
Thus, this chapter is devoted to the study of recursively defined discrete functions and the
solutions of recurrence relations associated to these recursively defined functions.
Definition: If f is a function that maps the set of whole numbers W or any non-empty
finite subset of W in to a certain number set, then the range of f is called a
sequence. By convention, the elements of the range of the function f, i.e. the
elements of the sequence are known as terms.
Note: A sequence is often called a discrete function or a numeric function.
Notations:
(1) Subscripted symbols of the form an, bn, fn, etc are used to denote the image of a whole
number n under the sequence f. If we select, say an to denote the image of nW under f, then
an = f(n), n= 0,1,2, …
(2) We use the notation {fn} n 0 or simply {fn} to denote a sequence f.
In other words,
{an} n 0 = {f0, f1, f2, ---} = the range of f (which is the sequence f).
If nW begins at some non negative integer k 1, then the notation {an} n k is applied for the
sequence.
2.3 Recursive Definition and Recurrence Relations
2.3.1 Recursive Definition
A technique of defining an algorithm, a set or a function in terms of itself by:
(i) Giving a rule for finding present and future values from earlier or prior values.
(ii) Specifying one or more starting values to activate the rule mentioned in (i)
An algorithm, a set or a function stated in terms of these two conditions is called a recursively
defined algorithm, set or function, respectively.
Note that a recursive definition is well defined if and only if it satisfies conditions (i) and (ii)
above. If any one of these two properties is lacking, the recursive definition may not describe the
required phenomenon in a unique manner.
Example:
Let us use a geometric sequence to illustrate that both the rule and the starting values are really
essential in recursive definitions.
Recall that a geometric sequence is an infinite array of numbers, such as 5,15,45,135, …,
where the division of any term ,other than the first, by its immediate predecessor is a constant,
called the common ratio r. For our sequence this common ratio r is 3 since
15 45 135
       3. If ao,a1,a2, ---,are in a geometric sequence, then
5 15 45

1
 a1 a2 a3 a
   ...  n 1 =…= r, the common ratio. In this particular geometric sequence
a0 a1 a2 an
an+1= 3an, n  0 is the rule for finding present and future values from earlier or prior terms.

The equation an+1= 3an, n  0, does not, however, define a unique geometric sequence.
The sequence 7, 21, 63, 189, … also satisfies the relation. To pinpoint the particular sequence
described by an+1= 3an, we need to know one of the terms of that sequence as a starting value.
Hence,
an+1= 3an, n  0 and a0=5 uniquely defines the sequence 5,15,45,135,…, whereas
an+1 = 3an n  0 and a1=21 identifies 7,21,63,189, … as the geometric sequence under study.
2.3.2 Recurrence Relations and Initial Conditions
Recurrence relation:
A recurrence relation for a sequence {an} and a non negative integer no, is a formula that
expresses an in terms of one or more of the previous values a0, a1, … , an-1 of the sequence for all
integers n  n0.

Initial conditions: Initial conditions, which are also called boundary conditions of the
recurrence relation, are the values of one or more starting terms of the sequence specified in the
form ao= k , a1= r, etc.for some constants k, r  R.
Note that the computation of terms of a sequence from the recurrence relation is initiated by the
boundary conditions.
Explicit sequence: A function an = f(n) that defines the term an of a sequence {an} on the basis
of a non-negative integer n alone is called an explicit sequence of n.

Examples: The expression.

n! = n (n-1) !, for n  1 and
O! = 1 [i.e., if n=0, then n! = 1]
refers to itself when it uses (n-1) ! to describe n!. Moreover it contains:
(i) an initial condition (or base value) specified as: 0! =1 or if n=0, then n! =1.
(ii) a recurrence relation stated as: n!=n(n-1)!. Note that this is a recurrence relation
because the present value n! is defined in terms of (n-1)!.Thus the above expression is the
recursive definition of the factorial function
f(n) = n! , n  0.
Solution of a Relation:
If each term of an explicit sequence an = f(n),  n w satisfies a given recurrence relation, then
the explicit sequence (i.e., the explicitly defined sequence) {an} is called the solution of the
difference equation. The procedure followed to find the explicit sequence {an} that solves a
recurrence relation is called solving.
Exercise:
1. Show that the explicit sequence {an} where an= 2n+1-1 for n 1 is a solution of the
recurrence relation:
an= 3an-1 – 2an-2 , n 3.
2. Show that the sequence {fn} defined explicitly by fn= 2(-4)n +3 is a solution of the
recurrence relation fn = -3 fn-1+4 fn-2.

2
2.4 Linear Recurrence Relation with Constant Coefficient
A recurrence relation of the form:
cofn + c1 fn-1+ c2fn-2+ … + ck fn-k = f(n) … [1].
Where c0, c1, c2, … , ck are constants, is called a linear recurrence relation with constant
coefficients (LRRWCC).
Note: The relation in [1] is linear since each term fn fn-1, fn-2, …, fn-k. appear only in a power of
degree one.
ORDER OF RECURRENCE RELATION
If the constants c0 and ck in [1] are none zero, then relation [1] is known as the kth- order linear
recurrence relation with constant coefficients.
Note: The phrase “ kth – order “ mean that the present term fn of the relation depends on k
previous terms, fn-1, fn-2, …, fn-k.
Examples
1. The Fibonacci sequence defined by the recurrence relation: Fn= Fn-1+ Fn-2 , n  2 with the
initial conditions F0= 0 and F1= 1 is linear second-order.
2. aK+1 –5ak + 4ak-1- 6ak-2 = Ak+10 defined for k  3, together with the initial
7
conditions a0 = and a1= a2=5 is a third-order linear recurrence relation with
3
constant coefficients (LRRWCC of order-three).

HOMOGENEOUS RELATION
The recurrence relation [1] is called a kth – order linear homogeneous recurrence relation with
constant coefficients if and only if f(n)= 0 for all n  W.
NONHOMOGENEOUS RELATION
The recurrence relation [1] is called a kth – order linear nonhomogeneous recurrence relation
with constant coefficients if and only if f(n)  0 for some n W. That is, the relation:
cofn + c1fn-1+ c2fn-2+ … ckfn-k= f(n)  0 for some n W is termed as nonhomogeneous recurrence
relation with constant coefficients (LNRRWCC).
Note: Non homogeneous recurrence relation is also called Inhomogeneous RR.
Example:
The relation: ak = 5ak-1, - 8ak-2 ,k  2 with a0 =5 and a1= 2 is a 2nd –order LHRRWCC, while
7
ak= 5ak-1 –ak-2 +6ak-3+ 4k+10, k  3 with a0 = and a1= a2 =5 is a 3rd –order LNHRRWCC.
3
2.5 Solving Linear Homogeneous Recurrence Relations

It is a common place to apply inductive and deductive reasoning in solving both

homogeneous and non homogeneous linear recurrence relations. Note that inductive reasoning is
used for the purpose of suggesting a sound and reasonable solution to the given recurrence
relation, while deductive reasoning is employed in proving that the suggested solution is correct.
In addition to this, the following two properties regarding solutions of linear recurrence relations
play a vital roll.

3
PROPERTIES OF SOLUTIONS
The solutions of a linear recurrence relation have two important properties which may be stated
as follows.
(1) Multiplication Property: Multiplying any solution of a linear recurrence relation
by a non-zero constant gives another solution
(2) Addition Property: Adding two or more solutions of a linear recurrence relation
gives another solution.
SOLVING FIRST ORDER LINEAR HOMOGENEOS RELATIONS
One method of solving a first-order linear homogeneous recurrence relation is an
application of a repetitive procedure called RECURSION METHOD. The following example
may illustrate the recursion method, i.e., the procedure of reducing the terms successively to the
initial values and then compute the value of the function at any non negative integer n from these
base (or initial) values.
Examples
1. Solve the general first-order linear homogeneous RR with constant coefficients:
an = r an-1 , n  1 with an initial condition: a0 = c.
Note that the coefficient r and the initial value c are constants.
Solution: We solve this general LHRRWCC of order one by recursion. To this end, observe that:
an = r an-1
an-1 = r an-2
an-2 = r an-3 and so on.
Thus, substituting these and similarly obtained formulas successively in the difference equation,
we get:
an = an-1
= r (r an-2)
= r2 an-2
= r2 (r an-3)
= r3 an-3
= …….
= ……
= rk an-k … (for each k  n).
= ……
= rn-1 an- (n-1)
n-1
=r a1
= rn-1 (r a0)
= rn a0

4
 = crn … (since a0 = c is given).
So the solution of the given recurrence relation: an= ran-1, n  1 and a0 = c is the explicit
function of n given by
an = crn for all n  0 ///
GENERAL SOLUTION
A solution an of a recurrence relation that involves arbitrary constants is called a general
solution. A solution of the form: an = rn, without the constant c, is called a basic solution.
UNIQUE SOLUTION
A solution in which all the arbitrary constants in the general solution are replaced by specific
numbers is called a unique solution of the recurrence relation:
Note: A unique solution should satisfy both the recurrence relation (RR) and the initial
conditions (IC). Thus, to determine the unique solution, we use the initial conditions to
evaluate the specific values of the arbitrary constants, other than the value of r, in the general
solution.
2. Let n be the number of memory locations referenced by a certain computer program.
Suppose that the algorithm implemented by the program requires fn bytes of memory,
where fn depends on n. If fn is defined recursively by:
fn = 4fn-1, n  2 and f1 =3.
Then find the amount of bytes of memory required to implement the algorithm by the
program for all n  2.
Solution: The problem is indeed a problem of solving the given recurrence relation and its
initial condition.
Method 1 (Recursion Method)
Starting from the given RR, we proceed by recursion or a repetitive procedure as follows.
fn = 4fn-1
=4 (4fn-2) … Since fn-1 = 4fn-2
= 42fn-2
= 42 (4fn-3) …. Since fn-2 = 4fn-3
= 43fn-3
= …..
= 4n-kfn-k (for each k W and k  n)
= ……
= 4n-1fn-(n-1) (where k =n-1)
= 4n-1f1
= 4n-1(3) ….. Since f1=3 is the given initial condition.

5
 = 3(4)n-1
Thus, the unique solution to the recurrence relation is:
fn= 3(4)n-1, n 1.
Method 2
The general solution obtained in example1 may be applied in solving the recurrence relation at
hand. In other words, suppose that the difference equation has a general solution of the form:
fn= crn , n1.
Substituting this formula in: fn= 4fn-1, we have
Crn= 4crn-1
cr n 4cr n 1
 
cr n 1 cr n 1
 r=4
 fn = c(4)n.
Using the initial condition: f1= 3, where n=1, yields
C(4)1 = f1=3
 4c =3
3
 c= .
4
3
 fn= (4)n = 3(4)n-1
4
Therefore, the unique solution is:
fn =3(4)n-1n  1 ///
This agrees with the above solution obtained by recursion.
2.6. The Second-Order Recurrence Relation
A typical second-order linear homogeneous recurrence relation with constant coefficients
(LHRRWCC of order-two) has the form:
c0an + c1an-1+ c2an-2 = 0, n  2
with accompanying boundary conditions expressed usually as:
a0 = k0 and a1 = k1
where k0, k1, c0, c1, c2 are constants with c0, c2  0.
2.6.1. Solving Homogeneous Relations of Order Two
Recall, from section 2.5, that a first order linear homogeneous relation with constant
coefficients had a general solution: an = crn, where c and r are non-zero constants.
Based on this work (regarding the first order case), we shall seek a solution for the
second-order homogeneous recurrence relation with constant coefficients, that assumes the same
form: an = crn. Note that we are using inductive procedure to suggest a solution.
Now, consider the second-order LHRRWCC:
A0an +A1an-1+ A2 an-2 = 0, n  2 …. (*)

6
Assume that this relation has a solution of the form:
an= crn with c  0 and r  0.
Then, observe that the two subsequent terms are expressed as:
an-1 = crn-1 and an-2 = crn-2
substituting these formulas into the equation (*), we get:
A0 crn + A1crn-1+ A2crn-2 = 0
 crn-2 [A0r2+ A1r + A2] = 0.
Dividing throughout this last equation by crn-2  0, we get a second-degree (or quadratic)
equation in r, which will be given by:
A0r2 + A1r + A2 = 0.
Consequently, the discrete function {an} with an = crn is a solution of the 2nd – order recurrence
relation:
A0an + A1an-1 + A2an-2 = 0 if and only if the number r is a solution of the 2nd-degree equation:
A0 r2+ A1r + A2 = 0.
2.6.2. Characteristic Equation and Roots
Definition:
The characteristic equation of a homogeneous 2nd- order linear recurrence relation with
constant coefficients:
A0an + A1an-1 + A2an-2 = 0.
is the 2nd-degree equation in r, which may be written as:
A0r2 + A1r + A2 = 0.
The solutions r1 and r2 of the characteristic equation are called the characteristic roots of
the recurrence relation.
Note: (1) the characteristic equation and characteristic roots are also called auxiliary equation
and auxiliary roots, respectively.
Exxercise: find the characteristic equation of each of the following recurrence relations
1. fn = 3fn-1 -2fn-2, n > 2 with initial conditions: f1=3 and f2 = 7
2. yn= 6yn-1- 9yn-2, n>1, y0= 5 and y1= 3
Definition: A solution r is called a root of multiplicity m, m  2, if it is repeated m-times as a
root of the characteristic equation associated to the given recurrence relation.
Algorithm for Solving Homogenous Recurrence Relations
The essential steps for solving a linear homogeneous recurrence relation with constant
coefficients of any order are the following.
Suppose that the given kth order LHRRWCC is:
fn + a1fn-1+ a2fn-2+ a3fn-3 + … akfn-k = 0, n  k.
Then:
Step1: Write the characteristic equation of the difference equation which is the kth degree
polynomial equation:
rk + a1rk-1 + a2rk-2 + a3rk-3 + … + ak-1r + ak = 0.
Step2: Solve the auxiliary equation found in step 1 and determine all the characteristic
roots of this equation.
Step3: Write the general solution of the difference equation based on any one of the
following two cases.
Case (i): If there are k distinct characteristic roots, say r1, r2, r3, … , rk to the
equation obtained in step 1, then the general solution is of the form:
fn = A1r1n + A2r2n + A3r3n + … Ak rkn.

7
 Case (ii): If there is a root r of multiplicity m, 2  m  k, for the auxiliary equation
obtained in step 1, then the part of the general solution that involves the root r has
the form:
A0 rn + A1 nrn + A2n2rn + ….+ Am-1 nm-1rn
= (A0+ A1n+ A2n2 + Am-1nm-1) rn.
In addition to the repeated root r, if r1,r2, …., rk-m are the k-m remaining distinct roots, then the
general solution is:
fn = (A0 + A1n + A2n2 + … + Am-1 nm-1) rn+ c1r1n + … + ck-mrnk-m.
Step4: Use the boundary conditions to determine the constants A0, A1, --- , Am-1, … c1,
c2,… , ck-m in the general solutions found in step 3 (i) or 3 (ii).
Step5: Replace the specific values of the arbitrary constants obtained in step 4 and write
the unique solution.

Examples
1. Solve the recurrence relation
un+1 = 4un, n > 0 with the initial condition u0 = 5.
Solution:
 The characteristic equation of the recurrence relation is:
r =4 … since the auxiliary equation of a first order recurrence relation is a linear (1st
degree) equation.
 The characteristic root is then r = 4.
 The general solution, for some constant A, is: un = A(r )n = A(4)n.
 To determine the arbitrary constant A, use the initial condition u0 =5. That is, for n =0,
write: u0 = A(4)0 =5  A=5
 Replacing the specific number 5 for the arbitrary constant A, the unique solution of the
given recurrence relation will be:
Un = 5(4)n, n  0 ///

Note: The roots of a characteristic equation associated to a recurrence relation could be complex
numbers. Even then, our methods are still valid, but the way the solutions of the recurrence
relations are written is different. Since an understanding of these representations requires some
background in complex numbers, we suggest that an interested reader refer to a more advanced
treatment of recurrence relations.
2. Solve recurrence relation
yn= 6yn-1- 9yn-2, n>1, with its initial conditions y0= 5 and y1= 3.
Solution:
Step1: Writing characteristic equation.
The auxiliary equation of the given recurrence relation is the second degree equation:
r2= 6r – 9.
 r2- 6r + 9 = 0
Step2: Determine characteristic roots.
(r-3)2 = 0
 r =3 is a repeated or a double characteristic root.
Step3: Write a general solution.
Thus, by case (ii) of step3, the general solution of the recurrence relation at hand is:
yn= c (3)n + dn (3)n.

8
Step4: Use the initial conditions to determine constants in the general solution.
Now, using the initial conditions, we get
y0 = c(3)0+ d(0) (3)0 = 5
y1 = c(3)1+ d(1) (3)1 = 3
 c=5  c=5
3c +3d = 3 d= -4.

Step5: Write the unique solution.

Thus, the explicit function of n that solves the given relation is:
yn = 5(3)n - 4n (3)n = (5-4n) (3)n for n  0 ///
2.7 Linear Nonhomogeneous Recurrence Relations
A recurrence relation of the form:
c0an +c1an-1 + c2an-2+ … + ck an-k = f(n), n  k.
Where c0, c1, c2, … , ck are constants with c0, ck  0 and f(n)  0 for some n  W is called a kth -
order linear nonhomogeneous recurrence relation with constant coefficients (LNRRWCC of
order k).

METHODS OF SOLVING NONHOMOGENEOUS RELATIONS

The Method of Undetermined Coefficients
The method of undetermined coefficients is a method that relies upon the associated
homogeneous relation obtained when f(n) is replaced by 0. This method, therefore, considers a
general or a total solution to the nonhomogeneous relation to be the sum of two parts; which we
shall call the homogeneous solution and the particular solution.
To have a better insight to this method, consider the kth- order nonhomogeneous relation:
c0an+ c1an-1+ c2an-2+ … + ckan-k = f(n)
which is equivalent to:
c0an+ c1an-1+ … + ck an-k= 0 + f(n).
Thus, the relation can be separated into two parts, namely;
Homogeneous Part: c0an + c1an-1+ c2an-2 + … + ckan-k =0 and
Nonhomogeneous Part: c0an + c1an-1+ c2 an-2 + … + ck an-k = f(n).
The method of undetermined coefficients, then, solves the homogeneous and the
nonhomogeneous parts separately. If the homogeneous solution (the solution of homogeneous
part) and the particular solution (the solution of the nonhomogeneous part) are denoted by an(h)
and an(p) , respectively, then the general or total solution an is the sum of these two solutions:
an = an(h) + an(p).
Definitions
(1) A homogeneous solution denoted by an(h) is the solution that satisfies the linear
nonhomogeneous recurrence relation when the function f(n) is replaced by 0.
(2) The solution denoted by an(p) that solves the recurrence relation containing the function
f(n), i.e. , the nonhomogeneous part is called a particular solution.
(3) The solution: an = an(h) + an(p) , which is the sum of the homogeneous solution and the
particular solution, is called the general solution or the total solution of the linear
nonhomogeneous recurrence relation with constant coefficients.
It is self evident that we need to find a homogeneous solution an(h) and a particular solution an(p)
to arrive at a total or a complete solution of any nonhomogeneous relation. To this effect, note
that

9
 (1) The homogeneous solution an(h) is obtained by the application of the standard methods of
solving linear homogeneous recurrence relations with constant coefficients discussed in
the preceding units of this chapter.
(2) As said earlier, there is no general technique for determining the particular solution an(p)
that fits a given difference equation. However, when the function f(n) has a certain form,
we can inductively suggest its form (i.e., the form of an(p) ), in line with the nature of f(n).
Table 2.2. beneath may be used as a guide-table in choosing a suitable particular
solution an(p).

GUIDE-TABLE

No. Nature of the function f (n) Choice of the particular solution: an(p)

1 f(n) = c is a constant function an(p) = A is also a constant

2 f(n) = nk or an(p) = A0+ A1n +A2n2+ … + Aknk is also

f(n)= b0+b1n+b2n2+ … + bknk a polynomial of degree k in n
is a polynomial function of degree
k in n

3 f(n) = rn is an exponential Arn, if r is not a characteristic

function, where r  R+ root of the homogeneous case.
an(p) =
Anmrn,, if r is a characteristic root
of multiplicity m  1 for
the homogeneous case

4 f(n) = nkrn or rn(A0+A1n+ … Aknk), if r is not

f(n) = (b0+ b1n+b2n2+ … + bknk) rn a characteristic root of the HRR.
is a product of any polynomial and an(p) =
exponential functions. nmrn (A0+ A1n+ … + Aknk) , if r is
a characteristic root of the HRR
with multiplicity m 1

Table 2.2
Remark:
The letters A, A0, A1, … , Ak-1, Ak denote constants called undetermined coefficients.
They will determined by substituting the particular solution an(p) into the given LNHRRWCC,
Furthermore, note that r, k and m are also constants.
We shall now illustrate the method of undetermined coefficients using the examples
below.

10
Examples

1. Solve the recurrence relation:

an- 7 an-1 + 12 an-2 = 1, n  2
with boundary conditions: a0 = 0 and a1 = 1.
Solution:
(1) Homogeneous Solution
The associated homogeneous relation is:
an – 7an-1+ 12an-2 = 0
and its characteristic equation is:
r2 –7r+12 = 0
 (r-3) (r-4) =0
 r1 = 3 and r2 = 4 are the characteristic roots.

Thus, the homogeneous solution is : an(h) = c1(3)n + c2 (4)n

(2) Particular solution
Since f(n) = 1 is a constant function, the particular solution is of the same form (see guide table
2.2).
an(p) = A, a constant to be determined (undetermined coefficient).
Substituting this suggested solution in the given nonhomogeneous relation:
an- 7an-1+ 12an-2 = 1,
We get:
A - 7A + 12A = 1
 6A = 1
1
 A=
6
1
So, the particular solution is: an 
( p)

6
(3) Total solution
Since the total solution is the sum of the homogeneous and the particular solutions:
an = an(h) + an(p),
then the required general (total) solution will be:
1
an = c1(3)n + c2(4)n + .
6
(4) Unique Solution
We finally solve for the arbitrary constants c1 and c2 in the total solution to obtain the solution
unique to the given recurrence relation. To this end, we use the initial conditions for the cases n=
0 and n=1. That is:
1
(n =0), a0 = c1 (3)0 + c2 (4)0 + = 0
6
1
(n = 1), a1 = c1 (3)1 + c2 (4)1 + = 1
6
1
c1+ c2 = -
6

11
 
5
3c1 + 4c2 = .
6
Upon solving this system of two equations, we get the values:
3 4
c1 = - and c2  .
2 3
Thus, the required unique solution of the given RR is:
3 4 1
an = - (3) n  (4)n  or
2 3 6
1 1 1
an = - (3)n 1  (4)n 1  , n  o //
2 3 6
2. Solve the relation;
an- 3an-1 = n, n  1 and a0 = 1
Solution:
(1) Homogenous solution
The associated homogenous recurrence relation is:
an – 3an-1 = 0
Thus, the characteristic equation is: r-3 = 0 which gives r = 3 as a characteristic root. So, the
homogeneous solution of the recurrence relation is:
an(h) =c (3)n
(2) Particular solution
Since f(n) = n is a polynomial function of degree one in n, the particular solution
is also a polynomial of degree one in n such that:
an(p)= A1n + A0

Substituting this solution in the given recurrence relation, we get:

(A1n + A0) –3 [A1(n-1) + A0] = n
 (-2A1) n+ (3A1- 2A0) = n

-2A1 = 1

3A1 – 2A0 = 0
1 3
 A1 = - and A0 = - .
2 4
1 3
Therefore, the particular solution is an(p) = - n-
2 4

12
(3) Total Solution
Since the total solution an is the sum of the homogeneous and particular solutions, it follows that
an = c(3)n - 1 n - 3 .
2 4
To evaluate the arbitrary constant c, we substitute the initial condition a0 = 1 in the total solution.
Thus
a0 = c(3)0 - 1 (0) - 3 = 1
2 4
3
 c- =1
4
7
 c= .
4
 Finally, the solution unique to the nonhomogeneous relation is:
7 1 3
an = (3)n - n - , n  0 ///.
4 2 4
3. Find the particular solution of the recurrence relation:
an + 5an-1 + 6an-2 = 3n2.
Solution:
f(n) =3n2  an(p) = A2n2 + A1n+ A0 by (2) of GUIDE TABLE 2.2.
Substituting the expression for an(p) in the RR:
an+ 5n-1 + 6an-2 = 3n2
 (A2n2 + A1n + A0) + 5 [ A2(n-1)2 + A1(n-1) + A0] + 6 [A2(n-2)2 + A1(n-2) +A0] =
3n2.
Upon simplifying, we get:

(12A2) n2 + (12A1- 34A2) n+(29A2- 17A1 + 12A0) = 3n2.

Equating coefficients of terms with the same powers of n on the two sides yields:

1
12A2 = 3 A2 
4
17
12 A1 – 34A2 = 0 so that A1 =
24
115
29 A2 – 17A1 + 12 A0 = 0 A0 = .
288

Thus, the required particular solution is:

1 17 115
an(p) = n2 + n+ ///
4 24 288
4. Solve the recurrence relation
an –4an-1 = 5(4)n, n  1, a0 =2
Solution: The associated homogeneous recurrence relation is an – 4an-1 = 0. It’s characteristic
equation is: r-4 = 0. Therefore, r =4 is the characteristic root. So, the
(h) n
homogeneous solution is : an = c(4) .

13
 Since f(n) = 5 (4)n is an exponential function and 4n is a homogeneous solution, the
particular solution will be: an(p)= An(4)n substituting this solution in the recurrence relation, we
get:
[An (4)n] – 4 [A(n-1)(4)n-1] = 5(4)n.
 An(4)n – 4An(4)n-1+ 4A(4)n-1 = 5(4)n
 An (4)n –An (4)n +A(4)n = 5(4)n
 A= 5.
Thus, the total solution is: an = c(4)n+ 5n(4)n. Using the initial condition a0 = 2 gives:
2 = c(4)0 + 5(0) (4)0  c=2
Hence, the complete (Unique) solution of the given recurrence relation is:
an = 2(4)n+ 5n (4)n, n  0 ///.

5. Find the particular solution of the recurrence relation

an+ an-1 = 3n(2)n.
Solution:
The function f(n) = 3n (2)n is a product of a polynomial and an exponential functions and, the
particular solution assumes the same form. That is:
an(p) =2n (A1n+ A0)
…. Item (4), Guide- Table 2.2.

Substituting this in the given recurrence relation gives:

(A1n+ A0) (2)n+ [A1(n-1) +A0] (2)n-1 = 3n(2)n
 2A1n+ 2A0+ A1n – A1 + A0 = 6n
 (3A1)n + (3A0 – A1) = 6n
Comparing the two sides of this resulting equation, we obtain:
3A1 = 6 and 3A0- A1 = 0.
2
 A1 = 2 and A0 = .
3
Consequently, the particular solution is:
2
an(p) = (2n+ ) (2)n
3
1
= ( + n) (2)n+1 ///
3

14