CFiniteSequence and CFiniteSequenceRing

C-finite sequences

Sublasses rec_sequences.DFiniteSequenceRing and defines sequences satisfying a linear recurrence equation with constant coefficients. Such a C-finite sequence \(a(n)\) is defined by a recurrence

\[c_0 a(n) + \dots + c_r a(n+r) = 0 \text{ for all } n \geq 0\]

and initial values \(a(0),...,a(r-1)\). In the background, we use the ore_algebra package to perform all operations.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *

sage: C = CFiniteSequenceRing(QQ) # create C-finite sequence ring over QQ

sage: f = C([1,1,-1], [0,1]) # define Fibonacci numbers
sage: f[:10] # get first 10 terms
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

sage: n = var("n");
sage: a = C(2^n) # define an exponential sequence
sage: a.normalized()
C-finite sequence a(n): (-2)*a(n) + (1)*a(n+1) = 0 and a(0)=1
sage: a.closed_form()
2^n

sage: b = a+f
sage: b.order()
3

sage: b.is_positive()
True

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

Bases: rec_sequences.DFiniteSequenceRing.DFiniteSequence

A C-finite sequence, i.e. a sequence where every term can be determined by a linear recurrence with constant coefficients and finitely many initial values. We assume that this recurrence holds for all values.

__getitem__(n)

Return the n-th term of self.

INPUT:

• n – a natural number or a slice object

OUTPUT:

The n-th sequence term of self (starting with the 0-th, i.e. to get the first term one has to call self[0]) if n is a natural number. If n is a slice object, the corresponding section of the sequence is returned.

An error is raised if no upper bound in the slice object is specified.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: c = C([1,1,-1], [0,1])
sage: c[-5:5]
[5, -3, 2, -1, 1, 0, 1, 1, 2, 3]

sage: d = C([2,1],[1])
sage: d[7]
-128

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

Construct a C-finite sequence \(a(n)\) with recurrence

\[c_0 a(n) + \dots + c_r a(n+r) = 0 \text{ for all } n \geq 0\]

from given list of coefficients \(c_0, ... , c_r\) and given list of initial values \(a(0), ..., a(r-1)\).

INPUT:

• parent – a CFiniteSequenceRing

• coefficients – the coefficients [c0,...,cr] of the recurrence

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

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

OUTPUT:

A C-finite sequence determined by the given recurrence and initial values.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: C([1,-2], [1])
C-finite sequence a(n): (1)*a(n) + (-2)*a(n+1) = 0 and a(0)=1

_add_(right, compress=True)

Return the sum of self and right. We use the method lclm from the OreAlgebra package to get the new annihilator.

INPUTS:

• right – C-finite sequences over the same C-finite sequence ring as self

• compress (default: True) – boolean specifying whether the resulting sequence should be expressed with a recurrence as small as possible

OUTPUTS:

The addition of self with right.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: a = C([2,-1], [1])
sage: b = C([3,-1], [1])
sage: a+b
C-finite sequence a(n): (6)*a(n) + (-5)*a(n+1) + (1)*a(n+2) = 0 and 
a(0)=2 , a(1)=5

_eq_(right)

Return whether the two CFiniteSequences self and right are equal. This is done by checking if enough initial values agree.

INPUT:

• right – a CFiniteSequence

OUTPUT:

True if the sequences are equal at every term and False otherwise.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ) 

sage: a = C([2,-3,1], [1,2])
sage: b = C([2,-1], [1])
sage: c = C([2,-1], [2])
sage: a==b
True
sage: a==c
False
sage: C(1) == 1
True
sage: 2 == C(1)
False

_latex_(name=None)

Creates a latex representation of the sequence. This is done by creating the latex representation of the closed form.

OUTPUT:

A latex representation showing the closed form of the sequence.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: print(latex(C([1/2,-1], [1])))
\left(\frac{1}{2}\right)^{n}

_mul_(right, compress=True)

Return the product of self and right. The result is the termwise product (Hadamard product) of self and right. To get the cauchy product use the method cauchy(). _mul_ uses the method symmetric_product of the ore_algebra package to get the new annihilator.

INPUTS:

• right – C-finite sequences over the same C-finite sequence ring as self

• compress (default: True) – boolean specifying whether the resulting sequence should be expressed with a recurrence as small as possible

OUTPUTS:

The product of self with right.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: a = C([2,-1], [1])
sage: b = C([3,-1], [1])
sage: a*b
C-finite sequence a(n): (-6)*a(n) + (1)*a(n+1) = 0 and a(0)=1

_repr_(name=None)

Produces a string representation of the sequence.

INPUT:

• name (optional) – a string used as the name of the sequence; if not given, self.name() is used.

OUTPUT:

A string representation of the sequence consisting of the recurrence and enough initial values to uniquely define the sequence.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: C([1,1,-1], [0,1], name="f")
C-finite sequence f(n): (1)*f(n) + (1)*f(n+1) + (-1)*f(n+2) = 0 and 
f(0)=0 , f(1)=1        

cauchy(right)

Computes the Cauchy product of two sequences.

INPUT:

• right – C-finite sequences over the same C-finite sequence ring as self

OUTPUT:

The cauchy product of self with right

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: a = C([2,-1], [1])
sage: b = C([3,-1], [1])
sage: a.cauchy(b)
C-finite sequence a(n): (6)*a(n) + (-5)*a(n+1) + (1)*a(n+2) = 0 and 
a(0)=1 , a(1)=5

charpoly(ring=None)

Returns the characteristic polynomial of self. If a polynomial ring is given, the polynomial will be in this ring. If no ring is given, a symbolic expression in x will be given.

INPUT:

• ring (default: None) – a univariate polynomial ring which should contain the characteristic polynomial

OUTPUT:

The characteristic polynomial of self as an element in ring if given or as a symbolic expression in x otherwise.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: C([2,-1], [1]).charpoly()
-x + 2

sage: R.<y> = PolynomialRing(QQ)
sage: C([1,1,-1], [0,1]).charpoly(R)
-y^2 + y + 1

closed_form()

Uses the Sage-native CFiniteSequence to compute a closed form, i.e., a polynomial linear combination of exponential sequence and returns that closed form.

OUTPUT:

The closed form as an object in the symbolic ring.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: C([2,-1], [1]).closed_form()
2^n

sage: C([1,1,-1], [0,1]).closed_form()
sqrt(1/5)*(1/2*sqrt(5) + 1/2)^n - sqrt(1/5)*(-1/2*sqrt(5) + 1/2)^n

decompose_degenerate()

Decomposes the sequence into sequences which are not degenerate or zero.

OUTPUT:

A list of non-degenerate (or zero) sequences such that self is the interlacing of these sequences.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ) 

sage: n = var("n")
sage: seqs = C(2**n + (-2)**n).decompose_degenerate()
sage: len(seqs) == 2
True

sage: seqs = C(2**n + (-3)**n).decompose_degenerate()
sage: len(seqs) == 1
True  

dfinite(ring)

Returns self as D-finite sequence in the given ring with possibly shorter recurrence. There is a shorter recurrence if

• self satisfies a shorter C-finite recurrence or

• self has multiple eigenvalues.

INPUT:

• ring – a DFiniteSequenceRing

OUTPUT:

A sequence in the specified ring which is equal to self.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: from rec_sequences.DFiniteSequenceRing import *

sage: C = CFiniteSequenceRing(QQ) 
sage: D = DFiniteSequenceRing(QQ['n']) 

sage: c = C([1,-3,3,-1], [1,2,5])
sage: c.dfinite(D)
D-finite sequence a(n): (n^2 + 2*n + 2)*a(n) + (-n^2 - 1)*a(n+1) 
= 0 and a(0)=1

dominant_root()

Returns the dominant root of the sequence.

OUTPUT:

The root with maximal modulus of the characteristic polynomial as an element in QQbar if it exists. If it does not exist, a ValueError is raised.

factorial(R, s=None)

Returns the \(C^2\)-finite sequence \(a(n)=\prod_{i=s}^n c(i)\) in the given ring. This sequence will satisfy the recurrence

\[d(n) a(n) - a(n+1) = 0 \text{ for all } n \geq 0\]

where \(d(n)=c(n+1)\) for \(n \geq s-1\) and \(d(n)=1\) for \(n < s-1\). If \(s\) is not given, the smallest \(s\) such that \(c(s) \neq 0\) is chosen. In the case that \(c\) is the Fibonacci sequence, this sequence is called the Fibonorial numbers.

Note

It only makes sense to choose \(s\) in such a way that \(c(n) \neq 0\) for all \(n \geq s\). Otherwise, the sequence will be eventually zero.

INPUT:

• R – a ring of type rec_sequences.C2FiniteSequenceRing

• s (default: None) – a natural number

OUTPUT:

The \(C^2\)-finite sequence \(a(n)=\prod_{i=s}^n c(i)\) as an element of R.

EXAMPLES:

sage: from rec_sequences.C2FiniteSequenceRing import *
sage: from rec_sequences.CFiniteSequenceRing import *

sage: C = CFiniteSequenceRing(QQ)
sage: C2 = C2FiniteSequenceRing(QQ)

sage: f = C([1,1,-1], [0,1])
sage: f_fac = f.factorial(C2) # fibonorials A003266
sage: f_fac[:10]
[1, 1, 1, 2, 6, 30, 240, 3120, 65520, 2227680]

sage: l = C([1,1,-1], [2,1])
sage: l_fac = l.factorial(C2) # lucastorials A135407
sage: l_fac[:10]
[2, 2, 6, 24, 168, 1848, 33264, 964656, 45338832, 3445751232]

interlace(*others)

Returns the interlaced sequence of self with others.

INPUT:

• others – other C-finite sequences over the same C-finite sequence ring

OUTPUT:

The interlaced sequence of self with others.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: a = C([2,-1], [1])
sage: f = C([1,1,-1], [0,1])
sage: f.interlace(a)[:10]
[0, 1, 1, 2, 1, 4, 2, 8, 3, 16]

is_degenerate()

Checks whether a sequence is degenerate. This is a necessary but not sufficient condition for a sequence to have infinitely many zeros.

OUTPUT:

Returns True if the sequence is degenerate, i.e. the ratio of two distinct roots is a root of unity. Returns False otherwise.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ) 

sage: a = C([2,-1], [1])
sage: a.is_degenerate()
False

sage: b = C(10*[1,0,2])
sage: b.is_degenerate() 
True  

is_eventually_positive(bound_n=5, bound=0, strict=True, time=- 1)

Uses the Gerhold-Kauers methods (Algorithm 1 and 2 in [KP10]) to check whether the sequence is eventually positive. This is done by checking whether self.shift(n) is positive for n <= bound_n. The smallest such index is returned. For every n the given time (if given) and bound is used.

INPUT:

• bound_n (default: 5) – index up to which it is checked whether the sequences is positive from that term on.

• bound (default: 0) – length of induction hypothesis

• strict (default: True) – if False non-negativity instead of positivity is checked

• time (default: -1) – if positive, this is the maximal time (in seconds) after computations are aborted

OUTPUT:

Returns n from where the sequence on is positive. If no such index could be found, a ValueError is raised.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ) 

sage: C([1,1,-1], [0,1]).is_eventually_positive()
1
sage: C(10*[1,2]).is_eventually_positive(strict=True)
0

is_positive(bound=0, strict=True, time=- 1, wo_rec=False, depth=5)

The following methods are used to show positivity of the sequence:

1. Decomposes a sequence into sequences which have a unique dominant root and zero sequences and proves positivity of each sequence using a classical method based on the asymptotics provided that the sequences have a unique dominating root [OW14].

2. The Gerhold-Kauers method, Algorithm 1 in [KP10].

3. It is checked whether it can be shown that the sequence is eventually monotonously increasing (and positive up to that term). This is also iterated to show whether it can be checked that the difference is monotonously increasing, etc.

4. A variation of the Gerhold-Kauers method, Algorithm 2 in [KP10].

5. If for the C-finite representation of the sequence positivity could not be shown, the same is tried with a (possibly) shorter D-finite representation.

Note

Note, that a time limit has to be given in order to run through all possible sub-algorithms. If such a time limit is not given it is possible that the method does not terminate even though it could show positivity if a time limit were given.

INPUT:

• bound (default: 0) – length of induction hypothesis

• strict (default: True) – if False non-negativity instead of positivity is checked

• time (default: -1) – if positive, this is the maximal time (in seconds) after computations are aborted

• wo_rec (default: False) – if True, then the method does not try to check whether the sequence is eventually increasing and deduce positivity this way.

• depth (default: 5) – a natural number; the depth \(d\) used in showing that the \(d\)-th iterated forward difference \(\Delta^d c\) is positive.

OUTPUT:

Returns True if it is positive, False if it is not positive and raises a ValueError or a TimeoutError exception if it could neither prove or disprove positivity.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ, time_limit = 10) 

sage: C([1,1,-1], [0,1]).is_positive(strict=False)
True
sage: C(10*[1,2]) > 0
True
sage: C(10*[1,3,-2]).is_positive()
False
sage: n = var("n")
sage: C(n^2+1).is_positive(time=10) # long time
True
sage: n = var("n")
sage: C(2^n+1).is_positive(time=5)
True

is_positive_algo1(bound=0, strict=True, time=- 1)

Uses the Gerhold-Kauers methods, in particular Algorithm 1 in [KP10], to check whether the sequence is positive.

INPUT:

• bound (default: 0) – length of induction hypothesis

• strict (default: True) – if False non-negativity instead of positivity is checked

• time (default: -1) – if positive, this is the maximal time (in seconds) after computations are aborted

OUTPUT:

Returns True if it is positive, False if it is not positive and raises a ValueError exception if it could neither prove or disprove positivity. If the time runs out, a TimeoutError is raised.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ) 

sage: C([1,1,-1], [0,1]).is_positive_algo1(strict=False)
True
sage: C(10*[1,2]).is_positive_algo1()
True
sage: C(10*[1,3,-2]).is_positive_algo1()
False

is_positive_algo2(bound=0, strict=True, time=- 1)

Uses the Gerhold-Kauers methods, in particular Algorithm 2 in [KP10], to check whether the sequence is positive.

INPUT:

• bound (default: 0) – length of induction hypothesis

• strict (default: True) – if False non-negativity instead of positivity is checked

• time (default: -1) – if positive, this is the maximal time (in seconds) after computations are aborted

OUTPUT:

Returns True if it is positive, False if it is not positive and raises a ValueError exception if it could neither prove or disprove positivity. If the time runs out, a TimeoutError is raised.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ) 

sage: C([1,1,-1], [0,1]).is_positive_algo2(strict=False)
True
sage: C(10*[1,3,-2]).is_positive_algo2()
False
sage: n = var("n")
sage: C((1/2)^n+1).is_positive_algo2() # long time
True

is_positive_dominant_root(strict=True, time=- 1)

Uses a classical method for show positivity of a sequence using bounds derived from the closed form, cf. [OW14].

INPUT:

• strict (default: True) – if False non-negativity instead of positivity is checked

• time (default: -1) – if positive, this is the maximal time (in seconds) after computations are aborted

OUTPUT:

Returns True if it is positive, False if it is not positive and raises a ValueError or a TimeoutError exception if it could neither prove or disprove positivity.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ, time_limit = 10) 

sage: C([1,1,-1], [0,1]).is_positive_dominant_root(strict=False)
True
sage: C([1,1,-1], [0,1]).is_positive_dominant_root()
False
sage: n = var("n")
sage: C(n^2+1).is_positive_dominant_root()
True

is_positive_dominant_root_decompose(strict=True, time=- 1)

Decomposes the sequence into sequences which have a unique dominant eigenvalue and zero sequences and proves positivity of these sequences using is_positive_dominant_root(). This fails if one of the sequences does not have a unique dominating root. In this case, a ValueError is raised.

INPUT:

• strict (default: True) – if False non-negativity instead of positivity is checked

• time (default: -1) – if positive, this is the maximal time (in seconds) after computations are aborted

OUTPUT:

Returns True if it is positive, False if it is not positive and raises a ValueError or a TimeoutError exception if it could neither prove or disprove positivity.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ) 

sage: n = var("n")
sage: c = C(2**n + (-2)**n)
sage: c.is_positive_dominant_root_decompose(strict=False)
True
sage: c.is_positive_dominant_root_decompose()
False

is_squarefree()

Checks whether the characteristic polynomial is squarefree.

OUTPUT:

True if the characteristic polynomial of self is squarefree and False otherwise.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ) 

sage: a = C([1,-2,1], [1,2])
sage: a.is_squarefree()
False

sage: b = C([2,1], [1])
sage: b.is_squarefree()
True

log = <Logger CFin (WARNING)>

nonzero_trailing_coefficient()

Computes a natural number \(N\) and a sequence \(c\) such that self[n+N]=c[n] for all \(n\) and the sequence \(c\) has a nonzero trailing coefficient. In particular, the sequence \(c\) has e.g. a closed form.

OUTPUT:

A pair \((N, c)\) such that self[n+N]=c[n] for all \(n\).

normalized()

Returns a normalized version of the same sequence, i.e., the leading coefficient of the sequence is 1.

OUTPUT:

A C-finite sequence equal to self with a recurrence with leading coefficient 1.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ) 

sage: a = C([1,2], [1])
sage: a.normalized().coefficients()
[1/2, 1]

roots(exact=True, *args, **kwargs)

Returns all roots (also called eigenvalues) of the characteristic polynomial of the sequence as elements in the algebraic number field.

Any additional arguments are passed to Sage’s roots method.

INPUT:

• exact (default: True) – if True, the roots are returned as elements in QQbar. If False they are returned as elements in CBF. In case the roots are in CBF they are not guaranteed to be separated.

OUTPUT:

All roots of the recurrence.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: C([2,-1], [1]).roots(multiplicities=False)
[2]

sage: C([1,1,-1], [0,1]).roots()
[(-0.618033988749895?, 1), (1.618033988749895?, 1)]

sparse_subsequence(R, u=1, v=0, w=0, binomial_basis=False)

Returns the \(C^2\)-finite sequence \(c(u n^2 + vn + w)\) in the given ring.

Note

The sequence need to be defined in the given range. If the sequence cannot be extended to the negative numbers (if the trailing coefficient is zero), then the indices \(u n^2 + vn +w\) all have to be non-negative for every \(n\).

INPUT:

• R – a ring of type rec_sequences.DifferenceDefinableSequenceRing, usually a rec_sequences.C2FiniteSequenceRing

• u (default: 1) – an integer; if u==0 then the method subsequence() is used.

• v (default: 0) – an integer

• w (default: 0) – an integer

• binomial_basis (default: False) – a boolean; if True the sequence \(c(u \binom{n,2} + vn + w)\) is computed instead, i.e. the binomial basis is chosen instead of the monomial one.

OUTPUT:

The \(C^2\)-finite sequence \(c(u n^2 + vn + w)\) as element in R.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: from rec_sequences.C2FiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)
sage: C2 = C2FiniteSequenceRing(QQ)

sage: f = C([1,1,-1], [0,1]) # Fibonacci numbers
sage: # compute sequence f(n^2), A054783
sage: f_sq = f.sparse_subsequence(C2)
sage: f_sq.order()
2
sage: f_sq[:10] == [f[n^2] for n in range(10)]
True

sage: from sage.functions.other import binomial
sage: # compute sequence f(binomial(n,2)), A081667
sage: f_binom = f.sparse_subsequence(C2, binomial_basis=True)
sage: f_binom[:10]
[0, 0, 1, 2, 8, 55, 610, 10946, 317811, 14930352]
sage: f_binom[:10] == [f[binomial(n, 2)] for n in range(10)]
True

subsequence(u, v=0, guessing=1)

Returns the sequence self[floor(u*n+v)].

INPUT:

• u – a rational number

• v (default: 0) – a rational number

• guessing (default: \(1\)) – if positive, guessing is used to compute the subsequence if self.order() >= guessing.

OUTPUT:

The sequence self[floor(u*n+v)].

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: a = C([2,-1], [1])
sage: a.subsequence(3, 1).normalized()
C-finite sequence a(n): (-8)*a(n) + (1)*a(n+1) = 0 and a(0)=2

sage: f = C([1,1,-1], [0,1])
sage: f[:10]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
sage: f.subsequence(2)[:5]
[0, 1, 3, 8, 21]

sage: f.subsequence(2, guessing=1)[:5]
[0, 1, 3, 8, 21]

sum()

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

OUTPUT:

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

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: a = C([2,-1], [1])
sage: a.sum()
C-finite sequence a(n): (-2)*a(n) + (3)*a(n+1) + (-1)*a(n+2) = 0 
and a(0)=1 , a(1)=3            

sage: f = C([1,1,-1], [0,1])
sage: f.sum()[:10]
[0, 1, 2, 4, 7, 12, 20, 33, 54, 88]

to_dependencies(name=None)

Returns a string representing the sequence in a form the Mathematica package Dependencies expects.

to_sage(var_name='y')

Returns the sequence as a Sage C-finite sequence.

INPUT:

• var_name (default: “y”) – a string representing the variable name of the built-in sage C-finite sequence ring

OUTPUT:

The sequence as an element in the ring of C-Finite sequences in var_name over the field self.base_ring()

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: a = C([2,-1], [1]).to_sage()
sage: a
C-finite sequence, generated by -1/2/(y - 1/2)
sage: a.parent()
The ring of C-Finite sequences in y over Rational Field

class rec_sequences.CFiniteSequenceRing.CFiniteSequenceRing(field=Rational Field, time_limit=2, name=None, element_class=None, category=None)

Bases: rec_sequences.DFiniteSequenceRing.DFiniteSequenceRing

A Ring of C-finite sequences over a field.

Element

alias of rec_sequences.CFiniteSequenceRing.CFiniteSequence

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

Constructor for a C-finite sequence ring.

INPUT:

• field (default: QQ) – a field of characteristic zero over which the C-finite sequence ring is defined.

• time_limit (default: 2) – a positive number indicating the time limit in seconds used to prove inequalities.

OUTPUT:

A ring of C-finite sequences

..TODO:

If field is fraction field, change it to fraction ring of 
polynomial ring which
can be handled by the ore_algebra package.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: CFiniteSequenceRing(QQ)
Ring of C-finite sequences over Rational Field
sage: CFiniteSequenceRing(NumberField(x^2-2, "z"))
Ring of C-finite sequences over Number Field in z with defining
polynomial x^2 - 2

_element_constructor_(x, y=None, name='a', check=True, is_gen=False, construct=False, **kwds)

Tries to construct a sequence \(a(n)\).

This is possible if:

• x is already a sequence in the right ring.

• x is a list of field elements and y is a list of field elements. Then x is interpreted as the coefficients of the sequence and y as the initial values of the sequence, i.e. \(a(0), ..., a(r-1)\).

• x can be converted into a field element. Then it is interpreted as the constant sequence \((x)_{n \in \mathbb{N}}\)

• x is in the symbolic ring and y a variable, then values of x.subs(y=n) for integers n are created and a recurrence for this sequence is guessed. If y is not given, we try to extract it from x.

• x is a list, then guessing on this list is used to determine a recurrence.

• x is a univariate polynomial, then the sequence represents the polynomial sequence.

• x is a RecurrenceSequence, the first y terms are used to guess a C-finite sequence (if y is not given, 100 terms are used).

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: f = C([1,1,-1],[1,1])
sage: f
C-finite sequence a(n): (1)*a(n) + (1)*a(n+1) + (-1)*a(n+2) = 0 and 
a(0)=1 , a(1)=1

sage: f==C(f)
True

sage: C(1/7)[:5]
[1/7, 1/7, 1/7, 1/7, 1/7]

sage: n = var("n")
sage: C(2^n)[:5]
[1, 2, 4, 8, 16]

sage: C(10*[1,0])
C-finite sequence a(n): (1)*a(n) + (-1)*a(n+2) = 0 and a(0)=1 , 
a(1)=0

sage: R.<x> = PolynomialRing(QQ)
sage: C(x^2-1)[:5]
[-1, 0, 3, 8, 15]

sage: from rec_sequences.C2FiniteSequenceRing import *
sage: C2 = C2FiniteSequenceRing(QQ)
sage: a = C2([1, 1], [17])
sage: a_cfin = C(a)
sage: a_cfin
C-finite sequence a(n): (1)*a(n) + (1)*a(n+1) = 0 and a(0)=17

_latex_()

OUTPUT:

A latex representation of the C-finite sequence ring.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: print(latex(CFiniteSequenceRing(QQ)))
\mathcal{C}(\Bold{Q})
sage: print(latex(CFiniteSequenceRing(NumberField(x^3-2, "z"))))
\mathcal{C}(\Bold{Q}[z]/(z^{3} - 2))

_repr_()

OUTPUT:

A string representation of the C-finite sequence ring.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: CFiniteSequenceRing(QQ)
Ring of C-finite sequences over Rational Field
sage: CFiniteSequenceRing(NumberField(x^3-2, "z"))
Ring of C-finite sequences over Number Field in z with defining
polynomial x^3 - 2

base()

OUTPUT:

The base field of the C-finite sequence ring

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: CFiniteSequenceRing(QQ).base()
Rational Field

construction()

Shows how the given ring can be constructed using functors.

OUTPUT:

A functor F and a field K such that F(K)==self

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *

sage: C = CFiniteSequenceRing(QQ)
sage: F, K = C.construction()
sage: F._apply_functor(K) == C
True

static geometric(ratio, name='a')

Creates the C-finite sequence ratio^n over the field in which ratio lives.

INPUT:

• ratio – a number

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

OUTPUT:

The geometric C-finite sequence with given ratio and given name.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *

sage: CFiniteSequenceRing.geometric(5)
C-finite sequence a(n): (5)*a(n) + (-1)*a(n+1) = 0 and a(0)=1

guess(data, name='a', *args, **kwds)

From given values guess a C-finite sequence using the ore_algebra package.

INPUT:

• data – list of elements in the base field of the C-finite sequence ring

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

• algorithm (optional) – if “rec_sequences”, then another straightforward implementation for sequences over QQ is used.

• operator_only (optional) – if True only the ore-operator of the recurrence is returned.

All additional arguments are passed to the ore_algebra guessing routine.

OUTPUT:

A C-finite sequence with the specified terms as initial values. If no such sequence is found, a ValueError is raised.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: C.guess(10*[1,-1])
C-finite sequence a(n): (1)*a(n) + (1)*a(n+1) = 0 and a(0)=1
sage: C.guess([i for i in range(10)])
C-finite sequence a(n): (-1)*a(n) + (2)*a(n+1) + (-1)*a(n+2) = 0 
and a(0)=0 , a(1)=1

static polynomial(poly, name='a')

Creates the C-finite sequence representing the given polynomial over the ground field of the polynomial ring.

A polynomial of degree \(d\) satisfies a recurrence of order \(d+1\) with coefficients

\[\binom{d+1}{i} (-1)^{d+i} \text{ for } i=0,\dots,d+1\]

INPUT:

• poly – a polynomial over a univariate polynomial ring

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

OUTPUT:

The polynomial C-finite sequence represented by the given polynomial and with given name.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *

sage: R.<y> = PolynomialRing(QQ)
sage: CFiniteSequenceRing.polynomial(y+1)[:5]
[1, 2, 3, 4, 5]

random_element(order=2, *args, **kwds)

Return a random C-finite sequence.

INPUT:

• order (default 2) – the order of the recurrence of the random C-finite sequence

Any additional arguments are passed to the method computing the random coefficients.

OUTPUT:

A C-finite sequence with a random recurrence of order order and random initial values consisting of integers between -10 and 10.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: C.random_element(order=1) # random
C-finite sequence a(n): (-6)*a(n) + (3)*a(n+1) = 0 and a(0)=-8

random_element_from_initial_values(initial_values, *args, **kwds)

Return a random C-finite sequence with given initial values.

INPUT:

• initial_values– the initial values of the random recurrence

OUTPUT:

A C-finite sequence with a random recurrence and given initial values.

EXAMPLES:

sage: from rec_sequences.CFiniteSequenceRing import *
sage: C = CFiniteSequenceRing(QQ)

sage: C.random_element_from_initial_values([1,2])[:5] # random
[1, 2, 91/3, 1288/3, 54733/9]

class rec_sequences.CFiniteSequenceRing.CFiniteSequenceRingFunctor

Bases: rec_sequences.DFiniteSequenceRing.DFiniteSequenceRingFunctor

__init__()

Constructs a CFiniteSequenceRingFunctor.

_repr_()

Returns a string representation of the functor.

OUTPUT:

The string “CFiniteSequenceRing(*)”.