Recurrence Equation

A recurrence equation (also called a difference equation) is the discrete analog of a differential equation. A difference equation involves an integer function in a form like

(1)

where is some integer function. The above equation is the discrete analog of the first-order ordinary differential equation

(2)

Examples of difference equations often arise in dynamical systems. Examples include the iteration involved in the Mandelbrot and Julia set definitions,

(3)

with a constant, as well as the logistic equation

(4)

with a constant. Perhaps the most famous example of a recurrence relation is the one defining the Fibonacci numbers,

(5)

for and with .

Recurrence equations can be solved using RSolve[eqn, a[n], n]. The solutions to a linear recurrence equation can be computed straightforwardly, but quadratic recurrence equations are not so well understood.

The sequence generated by a recurrence relation is called a recurrence sequence.

Let

(6)

where the generalized power sum for , 1, ... is given by

(7)

with distinct nonzero roots , coefficients which are polynomials of degree for positive integers , and . Then the sequence with satisfies the recurrence relation

(8)

(Myerson and van der Poorten 1995).

The terms in a general recurrence sequence belong to a finitely generated ring over the integers, so it is impossible for every rational number to occur in any finitely generated recurrence sequence. If a recurrence sequence vanishes infinitely often, then it vanishes on an arithmetic progression with a common difference 1 that depends only on the roots. The number of values that a recurrence sequence can take on infinitely often is bounded by some integer that depends only on the roots. There is no recurrence sequence in which each integer occurs infinitely often, or in which every Gaussian integer occurs (Myerson and van der Poorten 1995).

Let be a bound so that a nondegenerate integer recurrence sequence of order takes the value zero at least times. Then , , and (Myerson and van der Poorten 1995). The maximal case for is

(9)

with

(10)

(11)

The zeros are

(12)

(Beukers 1991).