Linear Recurrent Sequences

This is a project of linear recurrent sequences (I've also implemented the sequences of closed formula).

A linear recurrent sequence is a recurrent sequence that, for some natural n, all the terms of the sequence starting at n+1 are a fixed linear combination (with coefficients in the complex field) of the last n terms.

One of the things I made is that, given a collection of complex numbers, to find a linear recurrent sequence of minimum order (order is what n represents in the last paragraph) which starts with the given numbers. For this purpose I've used some linear algebra objects.

Another thing was to find a majorant and a minorant for the order of the sum of two linear sequences, and to determine one case in wich that majorant is reached.

The main theory that I used is in 1 and here theory.dvi.gz(DVI format), (PostScript format) are some corollaries that I needed.

The implementation is made in Squeak , click here to download the code.

Things to do

Linear recurrent sequences

  1. The sequence of partial sums of a linear recurrent it's also linear recurrent, and a majorant for the order is k+1 (where k is the order of the first one).

    Another nice thing would be: given a linear recurrent a determine if exists another b that verifies " a is the sequence of partial sums of b "

  2. Ask for the closed formula of a given sequence (one way to do this is implementing Jordan's form, I've already implement it so if you want it just mail me).

  3. Define a multiplicative operation:

    The convolution (Cauchy's product) and term by term product are also linear reccurrent sequence operations (I don't have the proof of this, not even a majorant for the orders).

Build another kind of recurrent sequences

  1. Sequences with coefficients in K[X].
  2. Sequences with coefficients in the field of rational functions of K[X].
  3. Anything else that comes to your mind (the two last items are pretty interesting).

Eric Rodriguez Guevara 

Bibliography (in Spanish :-( , sorry)

[1] Juan Sabia ( ) , Susana Tesauri ( ) , Sucesiones Recursivas Lineales, Notas de Matematica , 5 (U.B.A. 1997) recursivas.dvi.gz (DVI format) (PostScript format)