3.1 INTRODUCTION
In mathematics, we often refer a function in terms of itself. For example, the factorial function
f(n) = n!, for n as integer, is defined as,
f(n) =
11
11for
forn
nf n n≤
−>RS
T.( )
(3.1)
Above definition states that f(n) equals to 1 whenever n is less than or equal to 1. How-
ever, when n is more than 1, function f(n) is defined recursively (function invokes itself). In
loose sense the use of f on right side of equation (3.1) result a circular definition for example,
f(2) = 2. f(1) = 2.1 = 2 and f(3) = 3. f(2) = 3*2 = 6.
Take another example of Fibonacci number series, which is defined as,
f 0 = 0 ; f 1 = 1 ; fn = fn–1 + fn–2 for n >1 (3.2)
To compute the Fibonacci numbers series, f 0 and f 1 are the base component so that
computation can be initiated. fn = fn–1 + fn–2 is the recursive component that viewed as recur-
sive equations. In equation (3.1) the base component is f(n) = 1 for n = 1 and recursive compo-
nent is f(n) = n. f(n – 1).
Recurrence equations arise very naturally to express the resources used by recursive
procedures. A recurrence relation defines a function over the natural number, say f(n) in terms
of its own value at one/more integers smaller than n. In others words, f(n) defines inductively.
As with all inductions, there are base cases to be defined separately, and the recurrence rela-
tion only applies for n larger than the base cases.
For discrete numeric functions (a 0 , a 1 , a 2 , ......, an,......), an equation relating an for any n
to one/more of ai’s (i < n) is the recurrence relation of the numeric functions. A recurrence
relation is also called a difference equation.
For example, let a numeric function an = (2^0 , 2^1 , 2^2 , ......, 2n, ......), then the function
expression of an = 2n for n ≥ 0. Same numeric function can be specified by another way. Since
the value of an is twice the value of an–1 for all n, so once we know the value of an–1 we can
compute an. The value of an–1 is twice of an–2 which is again twice of an–3 and so on. Thus we
reach to a 0 whose value is known to be 1. Hence we write the relation
an = 2. an–1 for n ≥ 0 (3.3)
provided that a 0 = 1 is the recurrence relation that specify the numeric function an.
It is also clear that by recurrence relation, we can carry out step-by-step computation to
determine an from an–1, an–2, ......, to determine an+1 from an, an–1,.........and so on using base
conditions. We thus conclude that a numeric function can be described by a recurrence relation
3
Recurrence Relations with
Constant Coefficients
58