Demo: Inequalities of C- and D-finite Sequences

This is a short demo showing the methods available in the package.

Loading the package

The package requires the installation of the ErgoSum package (https://www.risc.jku.at/research/combinat/software/ergosum/) in a recent version. Then, the package can simply be loaded by:

<<RISC`PositiveSequence`;

PositiveSequence Package version 0.1 written by Philipp Nuspl
Copyright Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

Sequences

The package assumes that a C-finite sequence c defined by a recurrence 
	a0*c(n)+a1*c(n+1)+...+ar*c(n+r) = 0
and initial values c(0),...,c(r-1) is given in the syntax RE[{{0,a0,...,ar},{c(0),...,c(r-1)}},c[n]] where the initial zero in the coefficient list of the recurrence represents the zero in the (here) homogeneous recurrence. The GeneratingFunctions package provides methods to construct such a representation:

fib=DefineS[{c[n+2]==c[n+1]+c[n],c[0]==1,c[1]==1},c[n]]

For convenience, the PositiveSequence package also provides a method to construct a C-finite sequence from a symbolic expression using Guessing:

c2=SequenceFromExpression[2^n+3^n-(-1)^n,c[n]]

Using the GeneratingFunctions package one can naturally compute closure properties of those sequences or check equality.

Shift[fib,2]

fib*c2

fib+c2

fib==c2

Positivity

The main function to show positivity of a sequence is PositiveSequence[seq, Strict -> True, Verbose -> False]. If strict is True, then strict positivity is shown. If False, then non-negativity is shown.

?PositiveSequence

PositiveSequence[fib]

PositiveSequence[Shift[fib,-1]]

PositiveSequence[c2]

RE2L[c2-fib,10]

PositiveSequence[c2-fib,Strict->True]

PositiveSequence[c2-fib,Strict->False]

D-finite sequences

If the input to PositiveSequence is a D-finite sequence, Algorithms 1 and 2 from [Kauers, Pillwein 2010] is used to show positivity. Termination of these algorithms (in therefore of PositiveSequence) is not guaranteed. The following are the examples from the paper.

f1=RE[{{0,-(2n+7),3n+20,-(5n+22),2n+13},{1,1,1}},f[n]];
PositiveSequence[f1]

f2=RE[{{0,-(n+2),5n+12,-(5n+13),n+3},{1,1/4,1/10}},f[n]];
PositiveSequence[f2]

f3=RE[{{0,3n-16,-(3n-17)},{1}},f[n]];
PositiveSequence[f3]

u=1/2;
fRemark=RE[{{0,u,-(u+1),1},{1,2}},f[n]];
PositiveSequence[fRemark]

The algorithm, as expected, does not terminate for Example 4 from the paper.

f4=RE[{{0,(n+1)(n+4)/2,-(n+2)(3n+11)/2,(n+3)^2},{1,1/4}},f[n]];
PositiveSequence[f4,Strict->False]

Other algorithms

The algorithms KPAlgorithm1, KPAlgorithm2, AlgorithmDominantRootCAD, AlgorithmDominantRootClassic, AlgorithmCAD, AlgorithmClassic are implemented to show positivity of a C-finite sequence. The first two also support D-finite sequences. Check their documentation for further details, e.g.:

?KPAlgorithm1