|
Calling Sequence
|
|
MinimalRecurrence(R, dvar, init)
SumDecompose(R, dvar, init, Values)
GuessRecurrence(v, dvar, offset, Minimize)
|
|
Parameters
|
|
R
|
-
|
linear recurrence relation
|
dvar
|
-
|
dependent variable
|
init
|
-
|
set of initial conditions
|
Values
|
-
|
(optional) name; when specified, it is assigned a procedure that gives terms for each summand sequence
|
v
|
-
|
list of terms
|
offset
|
-
|
(optional) offset of a sequence (can be omitted if the offset is 0)
|
Minimize
|
-
|
(optional) literal; if specified, GuessRecurrence runs a part of MinimalRecurrence
|
|
|
|
|
Description
|
|
•
|
A sequence , , , ... is holonomic if it satisfies a linear homogeneous recurrence relation with polynomial or rational function coefficients. Given a recurrence, the dependent variable, and sufficiently many initial terms to define a sequence, the command MinimalRecurrence computes the recurrence of provably minimal order that holds for all but finitely many terms. Key to the proof are generalized exponents, from which degree bounds are be computed that are used to prove that no lower order recurrence will be missed.
|
•
|
For a holonomic sequence , given by a recurrence relation and initial terms, SumDecompose writes as a sum of holonomic sequences of lower order when possible: = + + ... where each is a holonomic sequence that can not be further decomposed as a sum of even lower order sequences. A holonomic sequence has a non-trivial sum decomposition if and only if the minimal operator of is an LCLM of lower order operators. SumDecompose computes an LCLM factorization of the minimal recurrence.
|
•
|
If satisfies a recurrence that is an LCLM of lower order recurrences , that have a non-trivial GCRD, then the sum decomposition which writes as a solution of plus a solution of is not unique because one can add any solution of the GCRD to , and subtract the same from . To express this non-uniqueness, parameters (i=1,2,...) will then appear in the optional output Values. Any choice for these parameters will give a correct sum decomposition.
|
•
|
If is a holonomic sequence, and if is a list of sufficiently many initial terms of , then GuessRecurrence computes a recurrence for . Similar functionality is provided by gfun[`listtorec`], however, GuessRecurrence tries orders and degrees that are as high as possible for the number of specified terms (minus some terms set aside for checking). If a sequence is holonomic, and if sufficiently many terms are specified, then the output will be a correct recurrence. However, given only finitely many terms, it is not possible to prove that a sequence is holonomic, and if so, how many terms are needed to find the correct recurrence, hence the name GuessRecurrence.
|
•
|
The optional argument offset is needed when the first element of is not . For instance, if the sequence starts with , , ... then the offset is 1. The optional literal argument Minimize causes GuessRecurrence, if it finds a recurrence, to run a part of MinimalRecurrence. It skips steps that can be slow when the guessed recurrence is not correct, so if the guessed recurrence is correct, to check or prove that its order is minimal, call MinimalRecurrence.
|
|
|
Examples
|
|
>
|
|
| (1) |
>
|
|
| (2) |
The Online Encyclopedia for Integer Sequences, oeis.org, gives this recurrence for sequence A000159:
>
|
|
| (3) |
Here are some initial values:
>
|
|
| (4) |
>
|
|
| (6) |
When init contains more initial conditions than necessary, MinimalRecurrence uses R to check them, which helps to detect mistakes.
>
|
|
| (7) |
Assuming the input R is correct, the output MinRec will be the recurrence with proved minimal order. A closed form expression for a(n) can be computed as follows: MinRec has a second order right factor that can be solved in closed form, and the remaining solution coming from the left-factor can be rounded to a closed form expression.
If a sequence is holonomic, and if sufficiently many terms are given, then GuessRecurrence will find a recurrence. Here are the first 65 terms of sequence A001455:
>
|
|
| (8) |
The offset for this sequence is 4, which means that v = [u(4), u(5), ...] (If the optional argument offset is omitted, then GuessRecurrence assumes that it is 0 and interpret v as [u(0),u(1),...]).
>
|
|
| (10) |
Without the optional argument Minimize, the output in this example would have been larger.
>
|
|
| (11) |
>
|
|
| (12) |
>
|
|
| (13) |
>
|
|
| (14) |
After looking up these last two sequences in oeis.org we discover that A001455(n) = A047889(n) - A005802(n)
>
|
|
| (15) |
>
|
|
| (16) |
| (17) |
In this last example, R, dvar, and init were not listed as separately in the input, but MinimalRecurrence (and SumDecompose) can deduce them when the set S has only one dependent variable, one recurrence relation, and all remaining elements are initial conditions.
|
|
References
|
|
|
M. van Hoeij. "Factoring Linear Recurrence Operators." URL www.math.fsu.edu/~hoeij/2019/slides.pdf
|
|
|
Compatibility
|
|
•
|
The LREtools[MinimalRecurrence], LREtools[SumDecompose] and LREtools[GuessRecurrence] commands were introduced in Maple 2021.
|
|
|
|