reducerecorder

gfun[reducerecorder] - Compute a smaller-order P-recurrence for a sequence.

Calling Sequence

reducerecorder(rec, u(n), nmax, procu, eqns, operator=name)

Parameters

rec - valid P-recurrence for u(n), u(n) - sequence and index names,

nmax - posint (optional); maximum number of initial conditions computed, such that u(0),...,u(nmax-1) are used for guessing,

procu - (optional) procedure which computes u(n). It should have remember option,

operator - (optional) name used verbatim as the shift operator; the default is equation,

eqns - (optional) equation(s) of the form option=value where option is nmin; nmin is the minimum number of initial conditions used for guessing. Output

A smaller order recurrence defining u(n) uniquely - possibly rec itself.

Description

The reducerecorder command attempts to compute a small-order recurrence equivalent to a given one. The recurrence looked for can be constrained regarding its minimal order and coefficients' sizes, using gfun:-Parameters options.
The input recurrence may be inhomogeneous. It is used to generate sequence terms for guessing, while its homogenization is used for the operator GCD.
With operator=name, the certification still uses the input initial data, but the result is returned as a polynomial in the supplied name and no final output initial conditions are constructed.
The procedure works as follows: - A new recurrence for u(n) is searched for, based on initial conditions : u(0), ..., u(i-1), with i increasing exponentially from nmin to nmax (included). - Once a recurrence of small order is found, enough initial conditions are associated, and it is checked to define the same (infinite) sequence.
This command is part of the gfun package, so it can be used in the form reducerecorder(..) only after executing the command with(gfun). However, it can always be accessed through the long form of the command by using gfun[reducerecorder](..).

Examples

reducerecorder may help getting information on the asymptotics of a sequence.

> with(gfun):

> rec := { 2*u(n+2)-5*u(n+1)+2*u(n)=0, u(0)=1, u(1)=2 };

\[\{2 u \! \left(n +2\right)-5 u \! \left(n +1\right)+2 u \! \left(n \right) = 0, u \! \left(0\right) = 1, u \! \left(1\right) = 2\}\]

> reducerecorder( rec, u(n), 10 );

\[\{-2 u \! \left(n \right)+u \! \left(n +1\right), u \! \left(0\right) = 1\}\]

> rec := { u(n+2) - (n+1)*X*u(n+1) - (2*n+4)*X^2*u(n), u(0)=1, u(1)=2*X };

\[\{u \! \left(n +2\right)-\left(n +1\right) X u \! \left(n +1\right)-\left(2 n +4\right) X^{2} u \! \left(n \right), u \! \left(0\right) = 1, u \! \left(1\right) = 2 X\}\]

> reducerecorder( rec, u(n), 10 );

\[\{\left(-X n -2 X \right) u \! \left(n \right)+u \! \left(n +1\right), u \! \left(0\right) = 1\}\]

It may simplify operators obtained by indirect means :

> rec := diffeqtorec(algeqtodiffeq( z+y(z)+y(z)^2+y(z)^4, y(z),{y(0)=0}), y(z), u(n));

\[\{\left(6144 n^{3}+3072 n^{2}-384 n -192\right) u \! \left(n \right)+\left(6400 n^{3}+36480 n^{2}+54608 n +23112\right) u \! \left(n +1\right)+\left(-896 n^{3}-14976 n^{2}-44140 n -35544\right) u \! \left(n +2\right)+\left(5176 n^{3}+40680 n^{2}+105056 n +88800\right) u \! \left(n +3\right)+\left(-1147 n^{3}-10323 n^{2}-29822 n -27528\right) u \! \left(n +4\right), u \! \left(0\right) = 0, u \! \left(1\right) = -1, u \! \left(2\right) = -1, u \! \left(3\right) = -2\}\]

> reducerecorder(rec,u(n),64);

\[\{\left(-35840 n^{4}-63232 n^{3}-20416 n^{2}+3952 n +1416\right) u \! \left(n \right)+4 \left(n +1\right) \left(4480 n^{3}+10144 n^{2}+6820 n +1371\right) u \! \left(n +1\right)-8 \left(2800 n^{2}+4940 n +1203\right) \left(n +1\right) \left(n +2\right) u \! \left(n +2\right)+31 \left(n +1\right) \left(n +2\right) \left(140 n^{2}+457 n +111\right) u \! \left(n +3\right), u \! \left(0\right) = 0, u \! \left(1\right) = -1, u \! \left(2\right) = -1\}\]

Description

Examples

See Also