Recurrence relations

 

A recurrence relation for the sequence  is an equation relating the term  to certain of the preceding , , for each

The recurrence relation is linear if it expresses  as a linear function of a fixed number of preceding terms. Otherwise the relation is nonlinear.

The recurrence relation is kth-order if  can be expressed in terms of  .

The recurrence relation is homogeneous if the zero sequence  satisfies the relation. Otherwise the relation is nonhomogeneous.

A kth-order linear homogeneous recurrence relation with constant coefficients is an equation of the form , , where the Ci  are real constants with Cn ≠ 0, Cn-k  ≠ 0. Initial conditions for this recurrence relation specify particular values for k of the ai  ( typically ).

Facts:

1. A kth-order linear homogeneous recurrence relation with constant coefficients can also be written , .

2. There are in general an infinite number of solution sequences  to a kth-order linear homogeneous recurrence relation (with constant coefficients).

3. A kth-order linear homogeneous recurrence relation with constant coefficients together with k initial conditions on consecutive terms  uniquely determines the sequence . This is not necessarily the case for nonlinear relations (see Example 2) or when nonconsecutive initial conditions are specified (see Example 3).

4. The same recurrence relation can be written in different forms by adjusting the subscripts. For examples, the recurrence relation , , can be written as , .

Examples:

1. The relation  , , is nonlinear homogeneous recurrence relation with constant coefficients. If the  initial conditions ,  are imposed, this defines an unique sequence  whose first few terms are 0, 1, 1, -1, -1, 3, 11, 115, . . . .

2. The first-order (constant coefficient) recurrence relation ,  is nonhomogeneous and non linear. Even though one initial condition are specified, this does not uniquely specify a solution sequence. Namely, the two sequences 1, -2, 1, 2, . . .  and 1, -2, -1, , . . . satisfy the  recurrence relation  and given initial condition.

3. The second-order recurrence relation , , with nonconsecutive initial conditions  does not uniquely specify a solution sequence. Both  and  satisfy the recurrence relation and given initial condition.