cfinite module

This module is a translation of (parts of) Doron Zeilberger’s CFinite.txt from Maple to Python. It contains classes and functions to do two things:

1. Work with linear recurrence relations with constant coefficients, called C-finite sequences or recurrences.

2. Guess possible C-finite recurrences a given list of terms might satisfy.

Code to do the second item already exists in sympy, but I thought it would be fun to write it again.

class cfinite.CFinite(initial, coeffs)

Bases: sympy.series.sequences.SeqBase

This class provides procedures for working with linear recurrence relations with constant coefficients, called C-finite sequences.

We inhereit from sympy’s SeqBase class, though our use is not currently (2017-09-20) optimized for recursion. (This goes for pisot.py as well.) SeqBase uses sympy’s @cacheit decorator, which we should try to take advantage of for recurrences. (For example, after computing CFinite.coeff(100), CFinite.coeff(99) is not cached.)

characteristic_poly(var=x)

Create the characteristic polynomial of the recurrence relation in var.

Var:Symbol to use as the polynomial’s variable. Returns:Sympy expression.

characteristic_roots()

Compute the roots of the characteristic equation.

Returns:List of roots returned by sympy.

default_assumptions = {'commutative': True}

gen()

Yield a generator of terms.

To compute terms, we will need to keep track of the previous degree terms. We need to access all of them, but also constantly delete the first term and add a new one. For simplicity, we currently use a list for this, despite the O(n) deletion. It is possible to use cyclic lists for O(1) runtime in both, should we wish later.

get_terms(k)

Compute the first k terms as a list.

interval

Interval on which sequence is defined ((0, \(\infty\))).

is_commutative = True

start

Start of sequence (0).

stop

End of sequence (\(\infty\)).

cfinite.guess_cfinite_degree(terms, degree)

Try to guess a C-finite recurrence of the given degree that the terms might satisfy.

If the terms do satisfy a linear recurrence relation, then they satisfy a certain linear system, where the coefficients of the recurrence are the unknowns, and the terms form the coefficient matrix. To try and guess what the coefficients should be, we form the system and try to solve it. If it works out, then we have a guess. If it doesn’t work out, then no possible C-finite recurrence can occur of the given degree.

Terms:Terms of the sequence. Degree:Degree of the recurrence to check. Returns:A CFinite instance, or None.

cfinite.guess_cfinite_recurrence(terms, max_degree=None)

Guess a C-finite recurrence that the terms might satisfy, up to a maximum degree.

Sympy has something that does this more efficiently, but I wanted to write my own that gives prettier error messages (see guess_cfinite_degree()).

Terms:Terms of the sequence. Max_degree:Maximum degree to check. Returns:A CFinite instance if a guess is found, otherwise None.