C-Finite Sequences¶
C-finite infinite sequences satisfy homogenous linear recurrences with constant coefficients:
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
See also
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 sequencesnames
– (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