C-Finite Sequences

C-finite infinite sequences satisfy homogeneous 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

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

Python

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

Sage Live

fibo = CFiniteSequence(x/(1-x-x^2))        # the Fibonacci sequence
fibo
fibo.parent()
fibo.parent().category()
C.<x> = CFiniteSequences(QQ)
fibo.parent() == C
C
C(x/(1-x-x^2))
C(x/(1-x-x^2)) == fibo
var('y')
CFiniteSequence(y/(1-y-y^2))
CFiniteSequence(y/(1-y-y^2)) == fibo

Finite subsets of the sequence are accessible via python slices:

Sage

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]

Python

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

Sage Live

fibo[137]                 #the 137th term of the Fibonacci sequence
fibo[137] == fibonacci(137)
fibo[0:12]
fibo[14:4:-2]

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

Sage

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

Python

>>> from sage.all import *
>>> r = C.from_recurrence([Integer(1),Integer(1)],[Integer(0),Integer(1)])
>>> r == fibo
True

Sage Live

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

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

Sage

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

Python

>>> from sage.all import *
>>> r = C.guess([Integer(0),Integer(1),Integer(1),Integer(2),Integer(3),Integer(5),Integer(8)])
>>> r == fibo
True

Sage Live

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

See also

fibonacci(), BinaryRecurrenceSequence

AUTHORS:

• Ralf Stephan (2014): initial version

REFERENCES:

• [GK1982]

• [KP2011]

• [SZ1994]

• [Zei2011]

class sage.rings.cfinite_sequence.CFiniteSequence(parent, ogf)

Bases: FieldElement

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

INPUT:

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

OUTPUT: a CFiniteSequence object

EXAMPLES:

Sage

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)

Python

>>> from sage.all import *
>>> CFiniteSequence((Integer(2)-x)/(Integer(1)-x-x**Integer(2)))     # the Lucas sequence
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)
>>> CFiniteSequence(x/(Integer(1)-x)**Integer(3))           # triangular numbers
C-finite sequence, generated by -x/(x^3 - 3*x^2 + 3*x - 1)

Sage Live

CFiniteSequence((2-x)/(1-x-x^2))     # the Lucas sequence
CFiniteSequence(x/(1-x)^3)           # triangular numbers

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

Sage

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

Python

>>> from sage.all import *
>>> CFiniteSequence(x**Integer(2)-Integer(4)*x**Integer(5))
Finite sequence [1, 0, 0, -4], offset = 2
>>> CFiniteSequence(Integer(1))
Finite sequence [1], offset = 0

Sage Live

CFiniteSequence(x^2-4*x^5)
CFiniteSequence(1)

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

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)

Python

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

Sage Live

CFiniteSequence(x^2+3/x)
CFiniteSequence(1/x+4/x^3)
P = LaurentPolynomialRing(QQ.fraction_field(), 'X')
X=P.gen()
CFiniteSequence(1/(1-X))

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

Sage

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

Python

>>> from sage.all import *
>>> CFiniteSequence(Integer(1)/(x-Integer(2)))
C-finite sequence, generated by 1/(x - 2)

Sage Live

CFiniteSequence(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

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

Python

>>> from sage.all import *
>>> var('x')
x
>>> f1 = CFiniteSequence((Integer(2)-x)/(Integer(1)-x-x**Integer(2)))
>>> P = QQ['x']; (x,) = P._first_ngens(1)
>>> f2 = CFiniteSequence((Integer(2)-x)/(Integer(1)-x-x**Integer(2)))
>>> f1 == f2
True
>>> f1.parent()
The ring of C-Finite sequences in x over Rational Field
>>> f1.ogf().parent()
Fraction Field of Univariate Polynomial Ring in x over Rational Field
>>> CFiniteSequence(log(x))
Traceback (most recent call last):
...
TypeError: unable to convert log(x) to a rational

Sage Live

var('x')
f1 = CFiniteSequence((2-x)/(1-x-x^2))
P.<x> = QQ[]
f2 = CFiniteSequence((2-x)/(1-x-x^2))
f1 == f2
f1.parent()
f1.ogf().parent()
CFiniteSequence(log(x))

closed_form(n='n')

Return a symbolic expression in n, which equals the n-th term of the sequence.

It is a well-known property of C-finite sequences a_n that they have a closed form of the type:

\[a_n = \sum_{i=1}^d c_i(n) \cdot r_i^n,\]

where r_i are the roots of the characteristic equation and c_i(n) is a polynomial (whose degree equals the multiplicity of r_i minus one). This is a natural generalization of Binet’s formula for Fibonacci numbers. See, for instance, [KP2011, Theorem 4.1].

Note that if the o.g.f. has a polynomial part, that is, if the numerator degree is not strictly less than the denominator degree, then this closed form holds only when n exceeds the degree of that polynomial part. In that case, the returned expression will differ from the sequence for small n.

EXAMPLES:

Sage

sage: CFiniteSequence(1/(1-x)).closed_form()
1
sage: CFiniteSequence(x^2/(1-x)).closed_form()
1
sage: CFiniteSequence(1/(1-x^2)).closed_form()
1/2*(-1)^n + 1/2
sage: CFiniteSequence(1/(1+x^3)).closed_form()
1/3*(-1)^n + 1/3*(1/2*I*sqrt(3) + 1/2)^n + 1/3*(-1/2*I*sqrt(3) + 1/2)^n
sage: CFiniteSequence(1/(1-x)/(1-2*x)/(1-3*x)).closed_form()
9/2*3^n - 4*2^n + 1/2

Python

>>> from sage.all import *
>>> CFiniteSequence(Integer(1)/(Integer(1)-x)).closed_form()
1
>>> CFiniteSequence(x**Integer(2)/(Integer(1)-x)).closed_form()
1
>>> CFiniteSequence(Integer(1)/(Integer(1)-x**Integer(2))).closed_form()
1/2*(-1)^n + 1/2
>>> CFiniteSequence(Integer(1)/(Integer(1)+x**Integer(3))).closed_form()
1/3*(-1)^n + 1/3*(1/2*I*sqrt(3) + 1/2)^n + 1/3*(-1/2*I*sqrt(3) + 1/2)^n
>>> CFiniteSequence(Integer(1)/(Integer(1)-x)/(Integer(1)-Integer(2)*x)/(Integer(1)-Integer(3)*x)).closed_form()
9/2*3^n - 4*2^n + 1/2

Sage Live

CFiniteSequence(1/(1-x)).closed_form()
CFiniteSequence(x^2/(1-x)).closed_form()
CFiniteSequence(1/(1-x^2)).closed_form()
CFiniteSequence(1/(1+x^3)).closed_form()
CFiniteSequence(1/(1-x)/(1-2*x)/(1-3*x)).closed_form()

Binet’s formula for the Fibonacci numbers:

Sage

sage: CFiniteSequence(x/(1-x-x^2)).closed_form()
sqrt(1/5)*(1/2*sqrt(5) + 1/2)^n - sqrt(1/5)*(-1/2*sqrt(5) + 1/2)^n
sage: [_.subs(n=k).full_simplify() for k in range(6)]
[0, 1, 1, 2, 3, 5]

sage: CFiniteSequence((4*x+3)/(1-2*x-5*x^2)).closed_form()
1/2*(sqrt(6) + 1)^n*(7*sqrt(1/6) + 3) - 1/2*(-sqrt(6) + 1)^n*(7*sqrt(1/6) - 3)

Python

>>> from sage.all import *
>>> CFiniteSequence(x/(Integer(1)-x-x**Integer(2))).closed_form()
sqrt(1/5)*(1/2*sqrt(5) + 1/2)^n - sqrt(1/5)*(-1/2*sqrt(5) + 1/2)^n
>>> [_.subs(n=k).full_simplify() for k in range(Integer(6))]
[0, 1, 1, 2, 3, 5]

>>> CFiniteSequence((Integer(4)*x+Integer(3))/(Integer(1)-Integer(2)*x-Integer(5)*x**Integer(2))).closed_form()
1/2*(sqrt(6) + 1)^n*(7*sqrt(1/6) + 3) - 1/2*(-sqrt(6) + 1)^n*(7*sqrt(1/6) - 3)

Sage Live

CFiniteSequence(x/(1-x-x^2)).closed_form()
[_.subs(n=k).full_simplify() for k in range(6)]
CFiniteSequence((4*x+3)/(1-2*x-5*x^2)).closed_form()

Examples with multiple roots:

Sage

sage: CFiniteSequence(x*(x^2+4*x+1)/(1-x)^5).closed_form()
1/4*n^4 + 1/2*n^3 + 1/4*n^2
sage: CFiniteSequence((1+2*x-x^2)/(1-x)^4/(1+x)^2).closed_form()
1/12*n^3 - 1/8*(-1)^n*(n + 1) + 3/4*n^2 + 43/24*n + 9/8
sage: CFiniteSequence(1/(1-x)^3/(1-2*x)^4).closed_form()
4/3*(n^3 - 3*n^2 + 20*n - 36)*2^n + 1/2*n^2 + 19/2*n + 49
sage: CFiniteSequence((x/(1-x-x^2))^2).closed_form()
1/5*(n - sqrt(1/5))*(1/2*sqrt(5) + 1/2)^n + 1/5*(n + sqrt(1/5))*(-1/2*sqrt(5) + 1/2)^n

Python

>>> from sage.all import *
>>> CFiniteSequence(x*(x**Integer(2)+Integer(4)*x+Integer(1))/(Integer(1)-x)**Integer(5)).closed_form()
1/4*n^4 + 1/2*n^3 + 1/4*n^2
>>> CFiniteSequence((Integer(1)+Integer(2)*x-x**Integer(2))/(Integer(1)-x)**Integer(4)/(Integer(1)+x)**Integer(2)).closed_form()
1/12*n^3 - 1/8*(-1)^n*(n + 1) + 3/4*n^2 + 43/24*n + 9/8
>>> CFiniteSequence(Integer(1)/(Integer(1)-x)**Integer(3)/(Integer(1)-Integer(2)*x)**Integer(4)).closed_form()
4/3*(n^3 - 3*n^2 + 20*n - 36)*2^n + 1/2*n^2 + 19/2*n + 49
>>> CFiniteSequence((x/(Integer(1)-x-x**Integer(2)))**Integer(2)).closed_form()
1/5*(n - sqrt(1/5))*(1/2*sqrt(5) + 1/2)^n + 1/5*(n + sqrt(1/5))*(-1/2*sqrt(5) + 1/2)^n

Sage Live

CFiniteSequence(x*(x^2+4*x+1)/(1-x)^5).closed_form()
CFiniteSequence((1+2*x-x^2)/(1-x)^4/(1+x)^2).closed_form()
CFiniteSequence(1/(1-x)^3/(1-2*x)^4).closed_form()
CFiniteSequence((x/(1-x-x^2))^2).closed_form()

coefficients()

Return the coefficients of the recurrence representation of the C-finite sequence.

OUTPUT: list of values

EXAMPLES:

Sage

sage: C.<x> = CFiniteSequences(QQ)
sage: lucas = C((2-x)/(1-x-x^2))   # the Lucas sequence
sage: lucas.coefficients()
[1, 1]

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> lucas = C((Integer(2)-x)/(Integer(1)-x-x**Integer(2)))   # the Lucas sequence
>>> lucas.coefficients()
[1, 1]

Sage Live

C.<x> = CFiniteSequences(QQ)
lucas = C((2-x)/(1-x-x^2))   # the Lucas sequence
lucas.coefficients()

denominator()

Return the numerator of the o.g.f of self.

EXAMPLES:

Sage

sage: f = CFiniteSequence((2-x)/(1-x-x^2)); f
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)
sage: f.denominator()
x^2 + x - 1

Python

>>> from sage.all import *
>>> f = CFiniteSequence((Integer(2)-x)/(Integer(1)-x-x**Integer(2))); f
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)
>>> f.denominator()
x^2 + x - 1

Sage Live

f = CFiniteSequence((2-x)/(1-x-x^2)); f
f.denominator()

numerator()

Return the numerator of the o.g.f of self.

EXAMPLES:

Sage

sage: f = CFiniteSequence((2-x)/(1-x-x^2)); f
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)
sage: f.numerator()
x - 2

Python

>>> from sage.all import *
>>> f = CFiniteSequence((Integer(2)-x)/(Integer(1)-x-x**Integer(2))); f
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)
>>> f.numerator()
x - 2

Sage Live

f = CFiniteSequence((2-x)/(1-x-x^2)); f
f.numerator()

ogf()

Return the ordinary generating function associated with the CFiniteSequence.

This is always a fraction of polynomials in the base ring.

EXAMPLES:

Sage

sage: C.<x> = CFiniteSequences(QQ)
sage: r = C.from_recurrence([2],[1])
sage: r.ogf()
-1/2/(x - 1/2)
sage: C(0).ogf()
0

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> r = C.from_recurrence([Integer(2)],[Integer(1)])
>>> r.ogf()
-1/2/(x - 1/2)
>>> C(Integer(0)).ogf()
0

Sage Live

C.<x> = CFiniteSequences(QQ)
r = C.from_recurrence([2],[1])
r.ogf()
C(0).ogf()

recurrence_repr()

Return a string with the recurrence representation of the C-finite sequence.

OUTPUT: string

EXAMPLES:

Sage

sage: C.<x> = CFiniteSequences(QQ)
sage: C((2-x)/(1-x-x^2)).recurrence_repr()
'homogeneous linear recurrence with constant coefficients of degree 2: a(n+2) = a(n+1) + a(n), starting a(0...) = [2, 1]'
sage: C(x/(1-x)^3).recurrence_repr()
'homogeneous linear recurrence with constant coefficients of degree 3: a(n+3) = 3*a(n+2) - 3*a(n+1) + a(n), starting a(1...) = [1, 3, 6]'
sage: C(1).recurrence_repr()
'Finite sequence [1], offset 0'
sage: r = C((-2*x^3 + x^2 - x + 1)/(2*x^2 - 3*x + 1))
sage: r.recurrence_repr()
'homogeneous linear recurrence with constant coefficients of degree 2: a(n+2) = 3*a(n+1) - 2*a(n), starting a(0...) = [1, 2, 5, 9]'
sage: r = CFiniteSequence(x^3/(1-x-x^2))
sage: r.recurrence_repr()
'homogeneous linear recurrence with constant coefficients of degree 2: a(n+2) = a(n+1) + a(n), starting a(3...) = [1, 1, 2, 3]'

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> C((Integer(2)-x)/(Integer(1)-x-x**Integer(2))).recurrence_repr()
'homogeneous linear recurrence with constant coefficients of degree 2: a(n+2) = a(n+1) + a(n), starting a(0...) = [2, 1]'
>>> C(x/(Integer(1)-x)**Integer(3)).recurrence_repr()
'homogeneous linear recurrence with constant coefficients of degree 3: a(n+3) = 3*a(n+2) - 3*a(n+1) + a(n), starting a(1...) = [1, 3, 6]'
>>> C(Integer(1)).recurrence_repr()
'Finite sequence [1], offset 0'
>>> r = C((-Integer(2)*x**Integer(3) + x**Integer(2) - x + Integer(1))/(Integer(2)*x**Integer(2) - Integer(3)*x + Integer(1)))
>>> r.recurrence_repr()
'homogeneous linear recurrence with constant coefficients of degree 2: a(n+2) = 3*a(n+1) - 2*a(n), starting a(0...) = [1, 2, 5, 9]'
>>> r = CFiniteSequence(x**Integer(3)/(Integer(1)-x-x**Integer(2)))
>>> r.recurrence_repr()
'homogeneous linear recurrence with constant coefficients of degree 2: a(n+2) = a(n+1) + a(n), starting a(3...) = [1, 1, 2, 3]'

Sage Live

C.<x> = CFiniteSequences(QQ)
C((2-x)/(1-x-x^2)).recurrence_repr()
C(x/(1-x)^3).recurrence_repr()
C(1).recurrence_repr()
r = C((-2*x^3 + x^2 - x + 1)/(2*x^2 - 3*x + 1))
r.recurrence_repr()
r = CFiniteSequence(x^3/(1-x-x^2))
r.recurrence_repr()

series(n)

Return the Laurent power series associated with the CFiniteSequence, with precision \(n\).

INPUT:

• n – nonnegative integer

EXAMPLES:

Sage

sage: C.<x> = CFiniteSequences(QQ)
sage: r = C.from_recurrence([-1,2],[0,1])
sage: s = r.series(4); s
x + 2*x^2 + 3*x^3 + 4*x^4 + O(x^5)
sage: type(s)
<class 'sage.rings.laurent_series_ring_element.LaurentSeries'>

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> r = C.from_recurrence([-Integer(1),Integer(2)],[Integer(0),Integer(1)])
>>> s = r.series(Integer(4)); s
x + 2*x^2 + 3*x^3 + 4*x^4 + O(x^5)
>>> type(s)
<class 'sage.rings.laurent_series_ring_element.LaurentSeries'>

Sage Live

C.<x> = CFiniteSequences(QQ)
r = C.from_recurrence([-1,2],[0,1])
s = r.series(4); s
type(s)

sage.rings.cfinite_sequence.CFiniteSequences(base_ring, names=None, category=None)

Return the commutative 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

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)

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> C
The ring of C-Finite sequences in x over Rational Field
>>> C.an_element()
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)
>>> C.category()
Category of commutative rings
>>> C.one()
Finite sequence [1], offset = 0
>>> C.zero()
Constant infinite sequence 0.
>>> C(x)
Finite sequence [1], offset = 1
>>> C(Integer(1)/x)
Finite sequence [1], offset = -1
>>> C((-x + Integer(2))/(-x**Integer(2) - x + Integer(1)))
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)

Sage Live

C.<x> = CFiniteSequences(QQ)
C
C.an_element()
C.category()
C.one()
C.zero()
C(x)
C(1/x)
C((-x + 2)/(-x^2 - x + 1))

class sage.rings.cfinite_sequence.CFiniteSequences_generic(polynomial_ring, category)

Bases: Parent, UniqueRepresentation

The class representing the ring of C-Finite Sequences.

Element

alias of CFiniteSequence

an_element()

Return an element of C-Finite Sequences.

OUTPUT: the Lucas sequence

EXAMPLES:

Sage

sage: C.<x> = CFiniteSequences(QQ)
sage: C.an_element()
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> C.an_element()
C-finite sequence, generated by (x - 2)/(x^2 + x - 1)

Sage Live

C.<x> = CFiniteSequences(QQ)
C.an_element()

fraction_field()

Return the fraction field used to represent the elements of self.

EXAMPLES:

Sage

sage: C.<x> = CFiniteSequences(QQ)
sage: C.fraction_field()
Fraction Field of Univariate Polynomial Ring in x over Rational Field

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> C.fraction_field()
Fraction Field of Univariate Polynomial Ring in x over Rational Field

Sage Live

C.<x> = CFiniteSequences(QQ)
C.fraction_field()

from_recurrence(coefficients, values)

Create a C-finite sequence given the coefficients \(c\) and starting values \(a\) of a homogeneous linear recurrence.

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

INPUT:

• coefficients – list of rationals

• values – start values, a list of rationals

OUTPUT: a CFiniteSequence object

EXAMPLES:

Sage

sage: C.<x> = CFiniteSequences(QQ)
sage: C.from_recurrence([1,1],[0,1])   # Fibonacci numbers
C-finite sequence, generated by -x/(x^2 + x - 1)
sage: C.from_recurrence([-1,2],[0,1])    # natural numbers
C-finite sequence, generated by x/(x^2 - 2*x + 1)
sage: r = C.from_recurrence([-1],[1])
sage: s = C.from_recurrence([-1],[1,-1])
sage: r == s
True
sage: r = C(x^3/(1-x-x^2))
sage: s = C.from_recurrence([1,1],[0,0,0,1,1])
sage: r == s
True
sage: C.from_recurrence(1,1)
Traceback (most recent call last):
...
ValueError: Wrong type for recurrence coefficient list.

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> C.from_recurrence([Integer(1),Integer(1)],[Integer(0),Integer(1)])   # Fibonacci numbers
C-finite sequence, generated by -x/(x^2 + x - 1)
>>> C.from_recurrence([-Integer(1),Integer(2)],[Integer(0),Integer(1)])    # natural numbers
C-finite sequence, generated by x/(x^2 - 2*x + 1)
>>> r = C.from_recurrence([-Integer(1)],[Integer(1)])
>>> s = C.from_recurrence([-Integer(1)],[Integer(1),-Integer(1)])
>>> r == s
True
>>> r = C(x**Integer(3)/(Integer(1)-x-x**Integer(2)))
>>> s = C.from_recurrence([Integer(1),Integer(1)],[Integer(0),Integer(0),Integer(0),Integer(1),Integer(1)])
>>> r == s
True
>>> C.from_recurrence(Integer(1),Integer(1))
Traceback (most recent call last):
...
ValueError: Wrong type for recurrence coefficient list.

Sage Live

C.<x> = CFiniteSequences(QQ)
C.from_recurrence([1,1],[0,1])   # Fibonacci numbers
C.from_recurrence([-1,2],[0,1])    # natural numbers
r = C.from_recurrence([-1],[1])
s = C.from_recurrence([-1],[1,-1])
r == s
r = C(x^3/(1-x-x^2))
s = C.from_recurrence([1,1],[0,0,0,1,1])
r == s
C.from_recurrence(1,1)

gen(i=0)

Return the i-th generator of self.

INPUT:

• i – integer (default: 0)

EXAMPLES:

Sage

sage: C.<x> = CFiniteSequences(QQ)
sage: C.gen()
x
sage: x == C.gen()
True

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> C.gen()
x
>>> x == C.gen()
True

Sage Live

C.<x> = CFiniteSequences(QQ)
C.gen()
x == C.gen()

gens()

Return the generators of self.

EXAMPLES:

Sage

sage: C.<x> = CFiniteSequences(QQ)
sage: C.gens()
(x,)

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> C.gens()
(x,)

Sage Live

C.<x> = CFiniteSequences(QQ)
C.gens()

guess(sequence, algorithm='sage')

Return the minimal CFiniteSequence that generates the sequence.

Assume the first value has index 0.

INPUT:

• sequence – list of integers

• algorithm – string; one of - 'sage' – the default is to use Sage’s matrix kernel function - 'pari' – use Pari’s implementation of LLL - 'bm' – use Sage’s Berlekamp-Massey algorithm

OUTPUT: a CFiniteSequence, or 0 if none could be found

With the default kernel method, trailing zeroes are chopped off before a guessing attempt. This may reduce the data below the accepted length of six values.

EXAMPLES:

Sage

sage: C.<x> = CFiniteSequences(QQ)
sage: C.guess([1,2,4,8,16,32])
C-finite sequence, generated by -1/2/(x - 1/2)
sage: r = C.guess([1,2,3,4,5])
Traceback (most recent call last):
...
ValueError: sequence too short for guessing

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> C.guess([Integer(1),Integer(2),Integer(4),Integer(8),Integer(16),Integer(32)])
C-finite sequence, generated by -1/2/(x - 1/2)
>>> r = C.guess([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
Traceback (most recent call last):
...
ValueError: sequence too short for guessing

Sage Live

C.<x> = CFiniteSequences(QQ)
C.guess([1,2,4,8,16,32])
r = C.guess([1,2,3,4,5])

With Berlekamp-Massey, if an odd number of values is given, the last one is dropped. So with an odd number of values the result may not generate the last value:

Sage

sage: r = C.guess([1,2,4,8,9], algorithm='bm'); r
C-finite sequence, generated by -1/2/(x - 1/2)
sage: r[0:5]
[1, 2, 4, 8, 16]

Python

>>> from sage.all import *
>>> r = C.guess([Integer(1),Integer(2),Integer(4),Integer(8),Integer(9)], algorithm='bm'); r
C-finite sequence, generated by -1/2/(x - 1/2)
>>> r[Integer(0):Integer(5)]
[1, 2, 4, 8, 16]

Sage Live

r = C.guess([1,2,4,8,9], algorithm='bm'); r
r[0:5]

Using pari:

Sage

sage: r = C.guess([1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28], algorithm='pari'); r
C-finite sequence, generated by (-x - 1)/(x^3 + x^2 - 1)
sage: r[0:5]
[1, 1, 1, 2, 2]

Python

>>> from sage.all import *
>>> r = C.guess([Integer(1), Integer(1), Integer(1), Integer(2), Integer(2), Integer(3), Integer(4), Integer(5), Integer(7), Integer(9), Integer(12), Integer(16), Integer(21), Integer(28)], algorithm='pari'); r
C-finite sequence, generated by (-x - 1)/(x^3 + x^2 - 1)
>>> r[Integer(0):Integer(5)]
[1, 1, 1, 2, 2]

Sage Live

r = C.guess([1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28], algorithm='pari'); r
r[0:5]

ngens()

Return the number of generators of self.

EXAMPLES:

Sage

sage: from sage.rings.cfinite_sequence import CFiniteSequences
sage: C.<x> = CFiniteSequences(QQ)
sage: C.ngens()
1

Python

>>> from sage.all import *
>>> from sage.rings.cfinite_sequence import CFiniteSequences
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> C.ngens()
1

Sage Live

from sage.rings.cfinite_sequence import CFiniteSequences
C.<x> = CFiniteSequences(QQ)
C.ngens()

polynomial_ring()

Return the polynomial ring used to represent the elements of self.

EXAMPLES:

Sage

sage: C.<x> = CFiniteSequences(QQ)
sage: C.polynomial_ring()
Univariate Polynomial Ring in x over Rational Field

Python

>>> from sage.all import *
>>> C = CFiniteSequences(QQ, names=('x',)); (x,) = C._first_ngens(1)
>>> C.polynomial_ring()
Univariate Polynomial Ring in x over Rational Field

Sage Live

C.<x> = CFiniteSequences(QQ)
C.polynomial_ring()

Make live