Mathematical Foundation of Computer Science

DHARM

RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 59

together with the base conditions. The numeric function is also referred to as the solution of the

recurrence relation.

In section 3.2 we will discuss a simple class of recurrence relations known as linear

recurrence relation with constant coefficients (LRRCC). Section 3.3 illustrates method for solving

of linear recurrence relation with constant coefficients. In this section we will discuss the

homogeneous solution and the particular solution of the differential equation along with an

alternate method discuss in section 3.4 where we will find out the solution through generating

function. We will also see that for a given set of base conditions the solution to a LRRCC is

unique. Common recurrences obtain from algorithms will be discussed in Section 3.5. We

describe several categories of recurrence equations obtain using algorithm paradigm such as

divide-and-conquer and chip-and-conquer and also the solution of these recurrences.

3.2 RECURRENCE RELATION FOR DISCRETE NUMERIC FUNCTIONS

(Linear Recurrence Relation with Constant Coefficients LRRCC)

A class of recurrence relation of the general form
A 0 an + A 1 an–1 + A 2 an–2 + ...... + Ak an–k = f(n) (3.4)
where Ai’s are constant (some may be zero) is known as linear recurrence relation with con-
stant coefficients (LRRCC) for some constant k ≥ 1.
For example, the Fibonacci recurrence equation (3.2) corresponds to k = 2 and f(n) = 0
with base conditions a 0 = 0 and a 1 = 1.
In the recurrence relation of equation (3.4) if coefficients A 0 and Ak are not zero then it
is kth order recurrence relation. For example, the recurrence relation 3 an + an–1 = n is a first
order LRRCC.
Consider another example,
an – 2an–1 + 3an–2 = n^2 +1 (3.5)
and an + an–2 + 5an–4 = 2n
are second-order and fourth-order LRRCC respectively. Also, the recurrence relation viz.
a^2 n + 3 an–1 = 5 is not a LRRCC.
Let us take the recurrence relation in (3.5), with base conditions a 3 = 1 and a 4 = 2. We
can compute a 5 as,
a 5 = 2 a 4 – 3 a 3 + (5^2 +1)
= 2 .2 – 3. 1 + 26 = 27
we then compute a 6 accordingly as,
a 6 = 2 a 5 – 3 a 4 + (6^2 +1)
= 2.27 – 3 .2 + 37 = 85
Similarly we determine a 7 , a 8 , ......and so on. We can also compute a 2 as,
a 2 = (1/3) ( a 4 – 2 a 3 – (4^2 +1))
= (1/3) ( 2 – 2 .1 – 17) = – 17/3
and so a 1 = 7/9 and a 0 = – 110/27. This way, we can completely specifiy the discrete numeric
function an.

FACT

In general, for the kth order LRRCC

1. If, k consecutive values of a numeric function are known then numeric function return
   unique solution.