Main Index Number Theory Sequences Recurrent sequences
Subject Index
comment on the page

Recurrence relations

A recurrence relation is an equation which is used to define a recurrent sequence recursively in the sense that each term of the sequence is defined as a function of the preceding terms. A recurrence relation is a specific type of  a difference equation involving differences between successive values of a function of a discrete variable.

A recurrent sequence is defined as

(1)

with the initial values , ... , . These values are called initial conditions. The number is the order of the relation (or equation).

If does not depend explicitly on then the recurrence relation is called autonomous, otherwise it is non-autonomous. For instance, the first order recurrence is non-autonomous, while is autonomous.

If the function is linear in then the recurrence (1) is called linear. Thus a th order linear recurrence has the form

(2)

If the recurrence relation is called homogeneous, otherwise inhomogeneous or non-homogeneous. If the coefficients does not depend on , they are constant we have a recurrence with constant coefficients.  

Solving a recurrence relation means obtaining a non-recursive function of .

Cite this web-page as: