RecurrenceSequenceElement and RecurrenceSequenceRing

This class provides common functionalities for rings of sequences defined by linear recurrence relations. The structure of the rings is given by:

So all rings are subclasses of a commutative algebra over a base field which is the field where all terms of the sequences live.

class rec_sequences.RecurrenceSequenceRing.RecurrenceSequenceElement(parent, coefficients, initial_values, name='a', is_gen=False, construct=False, cache=True)

Bases: sage.structure.element.CommutativeAlgebraElement

A sequence defined by a linear recurrence equation with some initial values.

__init__(parent, coefficients, initial_values, name='a', is_gen=False, construct=False, cache=True)

Construct a linear recurrence sequence \(a(n)\) with given coefficients of the recurrence and given initial values.

INPUT:

  • parent – a RecurrenceSequenceRing

  • coefficients – the coefficients of the recurrence

  • initial_values – a list of initial values, determining the sequence with at least order of the recurrence many values

  • name (default “a”) – a name for the sequence

OUTPUT:

A recurrence sequence determined by the given recurrence and initial values.

base()

Return the base of the parent of self.

base_ring()

Return the base field of the parent of self.

coefficients()

OUTPUT:

The coefficients of the recurrence of self as a list.

difference(i=1)

Returns the forward difference \(\Delta c = c(n+1)-c(n)\) of the sequence \(c\).

INPUT:

  • i (default: 1) – a natural number

OUTPUT:

The iterated forward difference sequence \(\Delta^i c\).

initial_values()

OUTPUT:

The initial values of self in form of a list.

is_gen()

OUTPUT:

Return False; the parent ring is not finitely generated.

is_unit()

Return True if self is a unit. We try to invert the element. If this is possible, the element is a unit, otherwise we return False.

OUTPUT:

True if the sequence is invertible and False otherwise.

is_zero()

Return whether self is the zero sequence \(0,0,0,\dots\). This is the case iff all the initial values are \(0\) or None.

Note

We circumvent Sage’s own is_zero implementation. This is because it calls __eq__ which calls __add__ which might itself check whether sequences are zero.

OUTPUT:

True if the sequence is constantly zero, False otherwise.

leading_coefficient()

OUTPUT:

The leading coefficient of the recurrence.

name()

OUTPUT:

The name of the sequence as a string.

nomial_coefficient(n, k, m=1)

Computes the term

\[\prod_{i=1}^k \frac{c(m(n-i+1))}{c(mi)}.\]

If \(c\) is the Fibonacci sequence, this is known as the fibonomial coefficient.

INPUT:

  • n – a positive integer

  • k – a positive integer

  • m (default: 1) – a positive integer

OUTPUT:

The coefficient of the sequence at the given term n.

order()

OUTPUT:

The order of the recurrence of self.

prec()

OUTPUT:

The precision of these objects is infinite.

prepend(values)

Prepends the given values to the sequence.

Input - values – list of values in the base ring

OUTPUT: A sequence having the same terms with the additional values at the beginning.

shift(k=1)

Shifts self k-times.

INPUT:

  • k (default: 1) – an integer

OUTPUT:

The sequence \((a(n+k))_{k \in \mathbb{N}}\).

sum()

Returns the sequence \(\sum_{i=0}^n c(i)\), the sequence describing the partial sums.

OUTPUT:

The sequence \(\sum_{i=0}^n c(i)\).

class rec_sequences.RecurrenceSequenceRing.RecurrenceSequenceRing(field=Rational Field, name=None, element_class=None, category=None)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.rings.ring.CommutativeAlgebra

A Ring of linear recurrence sequences over a field.

Element

alias of rec_sequences.RecurrenceSequenceRing.RecurrenceSequenceElement

__init__(field=Rational Field, name=None, element_class=None, category=None)

Constructor for a recurrence sequence sequence ring.

INPUT:

  • field – a field of characteristic zero over which the

    sequence ring is defined.

OUTPUT:

A ring of recurrence sequences.

_an_element_(*args, **kwds)

OUTPUT:

The Fibonacci sequence.

_eq_(right)

Tests if the two rings self``and ``right are equal. This is the case if they have the same class and are defined over the same base ring.

base()

OUTPUT:

The base field over which the sequence ring is defined

base_ring()

OUTPUT:

The base field over which the sequence ring is defined

construction()

Shows how the given ring can be constructed using functors.

OUTPUT:

A functor F and a ring R such that F(R)==self

is_commutative()

Returns whether self is a commutative ring. This is the case.

OUTPUT:

True

is_exact()

Returns whether self is an exact ring. This is the case.

OUTPUT:

True

is_field()

Returns whether self is a field. This is not the case.

OUTPUT:

False

is_finite()

Returns whether self is a finite ring. This is not the case.

OUTPUT:

False

is_integral_domain(proof=True)

Returns whether self is an integral domain. This is not the case.

OUTPUT:

False

is_noetherian()

Returns whether self is a Noetherian ring. This is not the case.

OUTPUT:

False

one()

OUTPUT:

The constant sequence \(1,1,\dots\).

zero()

OUTPUT:

The constant sequences \(0,0,\dots\).

class rec_sequences.RecurrenceSequenceRing.RecurrenceSequenceRingFunctor

Bases: sage.categories.pushout.ConstructionFunctor

__init__()

Constructs a RecurrenceSequenceRingFunctor.

merge(other)

Merge self with another construction functor, or return None.

Note

The default is to merge only if the two functors coincide. But this may be overloaded for subclasses, such as the quotient functor.

EXAMPLES:

sage: F = QQ.construction()[0]
sage: P = ZZ['t'].construction()[0]
sage: F.merge(F)
FractionField
sage: F.merge(P)
sage: P.merge(F)
sage: P.merge(P)
Poly[t]