C-Finite Sequences

C-finite infinite sequences satisfy homogenous linear recurrences with constant coefficients:

\[a_{n+d} = c_0a_n + c_1a_{n+1} + \cdots + c_{d-1}a_{n+d-1}, \quad d>0.\]

CFiniteSequences are completely defined by their ordinary generating function (o.g.f., which is always a fraction of polynomials over \(\ZZ\) or \(\QQ\) ).

EXAMPLES:

sage: fibo = CFiniteSequence(x/(1-x-x^2))        # the Fibonacci sequence
sage: fibo
C-finite sequence, generated by -x/(x^2 + x - 1)
sage: fibo.parent()
The ring of C-Finite sequences in x over Rational Field
sage: fibo.parent().category()
Category of commutative rings
sage: C.<x> = CFiniteSequences(QQ)
sage: fibo.parent() == C
True
sage: C
The ring of C-Finite sequences in x over Rational Field
sage: C(x/(1-x-x^2))
C-finite sequence, generated by -x/(x^2 + x - 1)
sage: C(x/(1-x-x^2)) == fibo
True
sage: var('y')
y
sage: CFiniteSequence(y/(1-y-y^2))
C-finite sequence, generated by -y/(y^2 + y - 1)
sage: CFiniteSequence(y/(1-y-y^2)) == fibo
False

Finite subsets of the sequence are accessible via python slices:

sage: fibo[137]                 #the 137th term of the Fibonacci sequence
19134702400093278081449423917
sage: fibo[137] == fibonacci(137)
True
sage: fibo[0:12]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
sage: fibo[14:4:-2]
[377, 144, 55, 21, 8]

They can be created also from the coefficients and start values of a recurrence:

sage: r = C.from_recurrence([1,1],[0,1])
sage: r == fibo
True

Given enough values, the o.g.f. of a C-finite sequence can be guessed:

sage: r = C.guess([0,1,1,2,3,5,8])
sage: r == fibo
True

AUTHORS:

  • Ralf Stephan (2014): initial version

REFERENCES:

[GK82]Daniel H. Greene and Donald E. (1982), “2.1.1 Constant coefficients - A) Homogeneous equations”, Mathematics for the Analysis of Algorithms (2nd ed.), Birkhauser, p. 17.
[KP11]Manuel Kauers and Peter Paule. The Concrete Tetrahedron. Springer-Verlag, 2011.
[SZ94]Bruno Salvy and Paul Zimmermann. - Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable. - Acm transactions on mathematical software, 20.2:163-177, 1994.
[Z11]Doron Zeilberger. “The C-finite ansatz.” The Ramanujan Journal (2011): 1-10.
sage.rings.cfinite_sequence.CFiniteSequence

Create a C-finite sequence given its ordinary generating function.

INPUT:

  • ogf – a rational function, the ordinary generating function (can be a an element from the symbolic ring, fraction field or polynomial ring)

OUTPUT:

  • A CFiniteSequence object

EXAMPLES:

sage: CFiniteSequence((2-x)/(1-x-x^2))     # the Lucas sequence
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)
sage: CFiniteSequence(x/(1-x)^3)           # triangular numbers
C-finite sequence, generated by -x/(x^3 - 3*x^2 + 3*x - 1)

Polynomials are interpreted as finite sequences, or recurrences of degree 0:

sage: CFiniteSequence(x^2-4*x^5)
Finite sequence [1, 0, 0, -4], offset = 2
sage: CFiniteSequence(1)
Finite sequence [1], offset = 0

This implementation allows any polynomial fraction as o.g.f. by interpreting any power of \(x\) dividing the o.g.f. numerator or denominator as a right or left shift of the sequence offset:

sage: CFiniteSequence(x^2+3/x)
Finite sequence [3, 0, 0, 1], offset = -1
sage: CFiniteSequence(1/x+4/x^3)
Finite sequence [4, 0, 1], offset = -3
sage: P = LaurentPolynomialRing(QQ.fraction_field(), 'X')
sage: X=P.gen()
sage: CFiniteSequence(1/(1-X))
C-finite sequence, generated by -1/(X - 1)

The o.g.f. is always normalized to get a denominator constant coefficient of \(+1\):

sage: CFiniteSequence(1/(x-2))
C-finite sequence, generated by 1/(x - 2)

The given ogf is used to create an appropriate parent: it can be a symbolic expression, a polynomial , or a fraction field element as long as it can be coerced into a proper fraction field over the rationals:

sage: var('x')
x
sage: f1 = CFiniteSequence((2-x)/(1-x-x^2))
sage: P.<x> = QQ[]
sage: f2 = CFiniteSequence((2-x)/(1-x-x^2))
sage: f1 == f2
True
sage: f1.parent()
The ring of C-Finite sequences in x over Rational Field
sage: f1.ogf().parent()
Fraction Field of Univariate Polynomial Ring in x over Rational Field
sage: CFiniteSequence(log(x))
Traceback (most recent call last):
...
TypeError: unable to convert log(x) to a rational
sage.rings.cfinite_sequence.CFiniteSequences(base_ring, names=None, category=None)

Return the ring of C-Finite sequences.

The ring is defined over a base ring (\(\ZZ\) or \(\QQ\) ) and each element is represented by its ordinary generating function (ogf) which is a rational function over the base ring.

INPUT:

  • base_ring – the base ring to construct the fraction field representing the C-Finite sequences
  • names – (optional) the list of variables.

EXAMPLES:

sage: C.<x> = CFiniteSequences(QQ)
sage: C
The ring of C-Finite sequences in x over Rational Field
sage: C.an_element()
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)
sage: C.category()
Category of commutative rings
sage: C.one()
Finite sequence [1], offset = 0
sage: C.zero()
Constant infinite sequence 0.
sage: C(x)
Finite sequence [1], offset = 1
sage: C(1/x)
Finite sequence [1], offset = -1
sage: C((-x + 2)/(-x^2 - x + 1))
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)
sage.rings.cfinite_sequence.CFiniteSequences_generic

The class representing the ring of C-Finite Sequences