Representations of sequences

 

A given infinite sequence  can often be represented in a more useful or more compact form. Namely, there may be a closed form expression for  as a function of n, the terms of the sequence may appear as coefficients in a simple generating function, or the sequence may be specified by a recurrence relation. Each representation has advantages, in either defining the sequence or establishing information about its terms.

Definitions:

A sequence   is a function from the set of nonnegative integers to the real numbers (often the integers). The terms of the sequence  are the values .

A closed form for the sequences  is an algebraic expression for as a function of n.

A recurrence relation is an equation expressing a term of a sequence as a function of  prior terms in the sequence.

A solution of a  recurrence relation is a sequence whose terms satisfy the relation.

The generating function for the  sequence  is the function  or any equivalent closed form expression.

The exponential generating function for the  sequence  is the function  or any equivalent closed form expression.

Examples:

1. The Fibonacci numbers Fn  arise in many applications and are given by the sequence 0, 1, 2, 3, 5, 8, 13, . . .  . This infinite sequence can be finitely encoded by means of the recurrence relation

 

Fn = Fn-1 + Fn-2  ,      n³2, with F0  = 0 and F1 = 1.

 

Alternatively, a closed form expression for this sequence is given by

 

    

The Fibonacci numbers can be represented in a third way, via the generating function  Namely, when this rational function is expanded in powers of x, the resulting coefficients generate the sequence values Fn:

 

 

2. Lucas numbers  are produced by the recursive definition ,

, n³2.