2 Notations and elementary results

In what follows, is the -th term of a sequence, while the associated generating function is noted so that

The sequence itself should be noted , but the notation is often used. For example, being the shift operator, notations and will be used indiferently. Section 3 will deal with the sequences (quadrat), (cross) and defined by :

In any context, denotes and not the generating function of .

When describing a second order linear recurrence, i.e. , it is convenient to introduce the roots , of the characteristic polynomial and rewrite this relation as :

The set of all sequences verifying Eq. 4 is a vector space, and the two sequences , are known to be a basis of this space (the special case has been postponed to subsec:alpha-equals-beta) so that every can be written as

The special status of this "geometric basis", i.e. of sequences and comes from the simplicity of these sequences, that can be expressed by their generating functions, namely

The generating function of a non geometric element of has two poles and can be written :

while the generating function of the shifted sequence is ;

Combining Eq. 6 and Eq. 7, we obtain that sequences and are geometric, namely :

In other words, the operators and are nothing but the projectors associated with the geometric basis. Multiplying side by side the two equations Eq. 8, we obtain the useful lemma :

where the determinant of a sequence is defined by :

and has the following property ;

Proposition 1  

Let be a sequence verifying recurrence Eq. 4. Then the vector space is spanned by and if and only if .

Let us now define the "generalized Fibonacci sequence associated with Eq. 4" by . Obviously, the (genuine) Fibonacci sequence is among them. The specificity of these sequences comes from the following :

Proposition 2 (Binet)  

Let be the generalized Fibonacci sequence associated with the recurrence Eq. 4. Then and is ever a basis of . And :