# Positivity certificates for linear recurrences

Alaa Ibrahim and Bruno Salvy<EMAIL_ADDRESS><EMAIL_ADDRESS>Univ
Lyon, EnsL, UCBL, CNRS, Inria, LIP, F-69342, LYON Cedex 07, France

###### Abstract.

We show that for solutions of linear recurrences with polynomial coefficients
of Poincaré type and with a unique simple dominant eigenvalue, positivity
reduces to deciding the genericity of initial conditions in a precisely
defined way. We give an algorithm that produces a certificate of positivity
that is a data-structure for a proof by induction. This induction works by
showing that an explicitly computed cone is contracted by the iteration of the
recurrence.

##  1\. Introduction

A sequence $(u_{n})_{n\in\mathbb{N}}$ of real numbers is called _P-finite_ if
it satisfies a linear recurrence

(1) $p_{d}(n)u_{n+d}=p_{d-1}(n)u_{n+d-1}+\dots+p_{0}(n)u_{n},\qquad
n\in\mathbb{N},$

with coefficients $p_{i}\in\mathbb{R}[n]$ (111Other names for such sequences
are _P-recursive_ [Sta80] and _holonomic_. The name P-finite was introduced by
Zeilberger [Zei90]. It is more consistent with the use of ‘C-finite’ for
constant coefficients and ‘D-finite’ for linear differential equations. It is
also the choice made in recent works by Kauers and Pillwein [Kau06, KP10].).
When the coefficients $p_{i}$ are constants in $\mathbb{R}$, the sequence is
called _C-finite_. If $p_{d}\neq 0$, the _order_ of the relation (1) is $d$.
If $0\not\in p_{d}(\mathbb{N})$, then the sequence is completely determined by
the recurrence and initial conditions $(u_{0},\dots,u_{d-1})$. We make this
assumption in the rest of this article. (222When it does not hold, the
sequence can be defined with extra initial conditions $u_{i+d}$ for $i$ s.t.
$p_{d}(i)=0$. For positivity questions, dealing with
$k:=\max(i\in\mathbb{N}\mid p_{d}(i)=0)$ initial values of the sequence
separately and considering the recurrence satisfied by
$(u_{n-k})_{n\in\mathbb{N}}$ reduces to the situation when $0\not\in
p_{d}(\mathbb{N})$.)

Given the polynomials $p_{i}$ and initial conditions, the _positivity problem_
is to decide whether $u_{n}\geq 0$ for all $n\in\mathbb{N}$ (333We call this a
problem of positivity rather than non-negativity to be consistent with the
terminology used in the C-finite case [OW14a]. The related problem to decide
whether $u_{n}>0$ for all $n\in\mathbb{N}$ is also of interest; our results
carry over to that case.). For instance, the rational sequence

(2)
$s_{n}=\sum_{k=0}^{n}{(-27)^{n-k}2^{2k-n}\frac{(3k)!}{k!^{3}}}\binom{k}{n-k}$

is not obviously positive. One way of proving its positivity is to use an
algorithm for recurrences of order 2, due to Kauers and Pillwein [KP10],
directly on the recurrence

$2(n+2)^{2}s_{n+2}=(81n^{2}+243n+186)s_{n+1}-81(3n+2)(3n+4)s_{n},\quad
s_{0}=1,s_{1}=12$

that can be computed by Zeilberger’s algorithm [PWZ96]. (Another proof was
given by Straub and Zudilin using hypergeometric identities [SZ15].) In this
work, we give an algorithm proving positivity of a large class of sequences of
arbitrary order, including those dealt with by the algorithm of Kauers and
Pillwein.

P-finite and C-finite sequences are closed under addition, product and Cauchy
product
$((u_{n})_{n\in\mathbb{N}},(v_{n})_{n\in\mathbb{N}})\mapsto(\sum_{k=0}^{n}u_{k}v_{n-k})_{n\in\mathbb{N}}$.
Also, for any $\ell\in\mathbb{N}_{>0}$ and $q\in\\{0,\dots,\ell-1\\}$, the
subsequence $(u_{\ell n+q})_{n\in\mathbb{N}}$ satisfies a linear recurrence
(of order at most $d$). These operations are all effective, so that
recurrences can be computed for these sequences given recurrences for the
input [Sta99]. These closure properties allow to reduce other problems to that
of positivity.

######  Example 1.

If $(u_{n})_{n\in\mathbb{N}}$ is a C-finite sequence of rational numbers and
$m$ is the lcm of the denominators of the initial conditions
$u_{0},\dots,u_{d-1}$ and of the coefficients $p_{0},\dots,p_{d-1}$, then the
sequence defined by $v_{n}=m^{n}u_{n}$ is a C-finite sequence of integers,
$(w_{n})_{n\in\mathbb{N}}=(v_{n}^{2}-1)_{n\in\mathbb{N}}$ is another C-finite
sequence of integers, which is positive if and only if $u_{n}\neq 0$ for all
$n$. This reduction of Skolem’s problem, which is notoriously difficult, to
positivity, shows that positivity is also likely to be hard [HHH06, OW14].

######  Example 2.

Deciding whether $u_{n}\geq v_{n}$ for all $n\in\mathbb{N}$ reduces to the
positivity of $(u_{n}-v_{n})_{n\in\mathbb{N}}$. Similarly, deciding that
$(u_{n})_{n\in\mathbb{N}}$ is increasing ($u_{n+1}\geq u_{n}$ for all $n$), or
convex ($u_{n+1}+u_{n-1}\geq 2u_{n}$) or log-convex ($u_{n+1}u_{n-1}\geq
u_{n}^{2}$) reduce to the positivity problem, by constructing recurrences for
these new sequences.

For applications of the positivity problem of C-finite sequences, we refer to
the numerous references in the work of Ouaknine and Worrell [OW14a].
Motivations for studying positivity in the more general context of P-finite
sequences also come from various areas of mathematics and its applications,
including number theory [SZ15], combinatorics [SS14], special function theory
[Pil08], or biology [MM22]. In computer science, the verification of loops
allowing multiplication by the loop counter leads to P-finite sequences
[HJK17, HJK18]. Such recurrences also occur in the floating-point error
analysis of simple loops obtained by discretization of linear differential
equations [Bol+14]. The positivity of sequences also plays a role for the
numerical stability of the computation of the sum of convergent power series
[Ser+16].

#### Previous works

For C-finite sequences of rational numbers, Ouaknine and Worrell have shown
decidability of positivity for recurrences of order up to 5, and a relation
between the decidability in higher order and the computability of the
homogeneous Diophantine approximation of a specific set of transcendental
numbers, a problem related to difficult questions in analytic number theory
[OW14a]. We refer to their work for earlier references. When the
characteristic polynomial of the sequence does not have multiple roots, this
extends to order up to 9. For reversible recurrences of integers (reversible
means that unrolling the recurrence backwards produces only integers for
negative indices), decidability of positivity is known for order up to 11
[Lip+22, Ken+23] and this goes up to 17 if the recurrence is both reversible
and with square-free characteristic polynomial [Ken+23]. Closer to our work,
for recurrences having one dominant eigenvalue, decidability is proven for
arbitrary order [OW14]. This is the property we use for P-finite sequences.

For P-finite sequences of order 1, positivity is easy. For order 2, it is
reducible to the problem of _minimality_ [Ken+21], itself a special case of
_genericity of initial conditions_ that appears in our work.

Another approach to the positivity of P-finite sequences starts with the work
of Gerhold and Kauers [GK05], who suggest to check for increasingly large $k$
whether

$u_{n}\geq 0\wedge u_{n+1}\geq 0\wedge\dots\wedge u_{n+k}\geq 0\Rightarrow
u_{n+k+1}\geq 0.$

Using the recurrence, this can be rewritten as a decision problem in the
existential theory of the reals. Gerhold and Kauers use cylindrical algebraic
decomposition [Col75] for this; other approaches are possible [BPR08, ch. 13].

They obtained several successes with this method, notably an automatic proof
of Turán’s inequality

$P_{n}(x)^{2}-P_{n-1}(x)P_{n+1}(x)\geq 0,\qquad x\in[-1,1]$

for the Legendre polynomials, that involves a parameter [GK06]. But
termination is not guaranteed in general and sufficient conditions for the
success of this method are unclear [KP10].

Kauers and Pillwein focused on the application of this method for P-finite
sequences [KP10]. They added the idea of looking for a proof of the stronger
inequality $u_{n+1}\geq\mu u_{n}$ for a well-chosen $\mu>0$. They showed that
this works for order 2 with generic initial conditions. They isolated a class
of recurrences of order 3 for which this approach also works. Pillwein [Pil13]
explored variants of this method and extended the class of recurrences that
can be handled with this type of method. Recently, Pei, Wang, Wang [PWW23]
revisited the case of order 2 and gave a simple way to compute $\mu$ as above,
and $N$ such that $u_{n+1}\geq\mu u_{n}>0$ for $n\geq N$.

#### Contributions

Our starting point is a result of Friedland on the convergence of products of
the successive elements of a convergent sequence of matrices [Fri06]. We make
explicit the effective aspects of some of his proofs and apply them to
questions of positivity. We deal with P-finite sequences of Poincaré type,
which means that after dividing by the leading coefficient and taking the
limit $n\rightarrow\infty$, each of the coefficients has a finite limit. (We
show in section 2.2 how to reduce to this case.) Moreover, we demand that the
characteristic polynomial of this new recurrence has only one root of maximum
modulus and that it is a simple root. Then, we show that, except for a
hyperplane of initial conditions, positivity can be proved by an induction
that proves $d(d-1)/2$ linear inequalities simultaneously. Note that for order
$d=2$, $d(d-1)=2$ is also the number of inequalities used by Kauers and
Pillwein.

These inequalities have a geometric nature: they describe a convex cone
containing the vector $(u_{n},u_{n+1},\dots,u_{n+d-1})$, bounded by $d(d-1)$
hyperplanes and contained in $\mathbb{R}_{>0}^{d}$. The proof by induction
consists in proving that successive vectors do not leave that cone. Our
algorithm thus produces that cone and an integer $N$ such that at index $N$,
the vector has entered the cone and no $u_{n}$ of smaller index is negative.
Capturing the geometry of the iteration by means of over-approximations by
cones or related geometric surfaces is natural in this context. For the less
general C-finite case and more general questions than positivity, related (but
distinct) surfaces have been used recently [Alm+22].

Like Friedland’s result, our approach applies to the more general situation of
a linear recurrence $U_{n+1}=A(n)U_{n}$, where $A(n)$ is a square matrix that
is invertible for all $n\geq 0$ and whose limit as $n\rightarrow\infty$ is
finite. For positivity, we further require that the limit has a unique
eigenvalue of maximal modulus and a corresponding eigenvector with positive
coordinates.

This work is structured as follows. First, background on eigenvalues and
asymptotics of linear recurrences is recalled in section 2. Section 3 presents
our result, the positivity certificates and how they are verified. The ideas
leading to the algorithm are presented in section 4, where we describe the
relevant tools from Friedland’s work. The algorithm is then given with its
proof in section 5.

##  2\. Background

###  2.1. Algebraic Coefficients

P-recursivity can be defined over arbitrary fields, but as we are interested
in positivity issues, it is natural to restrict our attention to subfields of
$\mathbb{R}$. More precisely, we denote by $\mathbf{Q}$ a field that is either
the field $\mathbb{Q}$ of rational numbers, or a real number field
$\mathbb{Q}(\alpha)$, where $\alpha$ is given, for instance, by a square-free
polynomial and an isolating interval [BPR08, Yap00]. In particular, with this
data structure, it is possible to determine the sign of an element of
$\mathbf{Q}$, where ‘sign’ means any of $<0$ or $>0$ or $=0$. From there,
using Sturm sequences, one can compute the number of roots of a polynomial in
$\mathbf{Q}[x]$ in an interval with endpoints that are either infinite or in
$\mathbf{Q}$. A direct consequence used repeatedly in this work is that one
can determine an integer beyond which a polynomial in $\mathbf{Q}[x]$ has
fixed sign. (For this problem, one can also use simple Cauchy-type bounds
[Mig92, Thm. 4.2].) In some cases, we also use the fact that these algorithms
extend to $\mathbf{Q}(\lambda)$ with $\lambda\in\mathbb{R}$ algebraic over
$\mathbf{Q}$.

###  2.2. Dominant Eigenvalues

If $U_{n}$ denotes the vector $(u_{n},\dots,u_{n+d-1})^{\mathsf{T}}$, the
linear recurrence (1) of order $d$ is a special case of a first-order linear
recurrence

(3) $U_{n+1}=A(n)U_{n},$

where $A(n)$ is the companion matrix

$A(n)=\begin{pmatrix}0&1&0&\dots&0\\\ 0&0&1&\dots&0\\\
\dots&\dots&\dots&\dots&\dots\\\ 0&0&0&\dots&1\\\
\frac{p_{0}(n)}{p_{d}(n)}&\frac{p_{1}(n)}{p_{d}(n)}&\frac{p_{2}(n)}{p_{d}(n)}&\dots&\frac{p_{d-1}(n)}{p_{d}(n)}\end{pmatrix},\qquad
n\in\mathbb{N}.$

The sequence $U_{n}$ is then recovered from the vector of initial conditions
by the matrix factorial $U_{n}=A(n-1)A(n-2)\dotsb A(0)U_{0}$.

######  Definition 1.

The linear recurrence (3) (and also (1) as a special case) is said to be of
_Poincaré type_ if the matrix $A:=\lim_{n\rightarrow\infty}A(n)$ is finite.

The motivation for considering this notion is that the finite case corresponds
to the situation of a linear recurrence with constant coefficients. Then the
P-finite case can be viewed as a perturbation of the C-finite case.

For linear recurrences of the type of eq. 1, being of Poincaré type is not a
strong restriction for positivity questions. If the recurrence is not of
Poincaré type, then one of the $p_{i}$ has degree higher than that of $p_{d}$.
This means that a solution behaves asymptotically like a rational power $p/q$
of $n!$. The maximal such power can be found by a Newton polygon [MS10] and
then one can consider the P-finite sequence obtained by multiplying $u_{n}$ by
the solution of $n^{p}u_{n+q}=u_{n}$, with initial conditions $(1,\dots,1)$.
The same operation can also be used if the matrix $A$ is nilpotent, using a
recurrence of the form $u_{n+q}=n^{p}u_{n}$ instead, so that we can always
assume that the recurrence is of Poincaré type, with $A$ having a nonzero
eigenvalue.

######  Definition 2 (Dominant eigenvalues).

Let $\lambda_{1},\dots,\lambda_{m}$ be the complex eigenvalues of the limit
matrix $A$, numbered by decreasing modulus so that

$|\lambda_{1}|=|\lambda_{2}|=\dots=|\lambda_{k}|>|\lambda_{k+1}|\geq|\lambda_{k+2}|\dots\geq|\lambda_{m}|.$

Then $\lambda_{1},\dots,\lambda_{k}$ are called the _dominant eigenvalues of
$A$_. We say that an eigenvalue is _simple_ when it is a simple root of the
characteristic polynomial.

Given a characteristic polynomial in $\mathbf{Q}[x]$, one can isolate the
dominant eigenvalues in polynomial complexity [GS96], see also [Bug+22].

###  2.3. Asymptotics

For C-finite sequences, a starting point is the closed-form

$u_{n}=\sum_{i=1}^{k}C_{i}(n)\lambda_{i}^{n}+\sum_{i>k}C_{i}(n)\lambda_{i}^{n},$

split into one sum over dominant eigenvalues and one sum over smaller ones.
Since the basis of solutions is known explicitly, the polynomials $C_{i}(n)$
can be computed easily from the initial conditions. They belong to
$\mathbf{Q}(\lambda_{1},\dots,\lambda_{m})[n]$.

The difficulty when using this formula to prove positivity is that for $k>1$,
the first sum contains oscillating sequences that can come very close to 0.
This is where tools from analytic number theory, such as Baker’s theorem on
linear forms in logarithms, come into play for deciding positivity [OW14a,
OW14, Ken+23].

For P-finite sequences the situation is made harder by the fact that there is
no ‘simple’ basis of solutions. Also, the constants that appear, even in the
leading coefficient, are difficult to relate to the initial conditions. This
is illustrated by the following.

######  Example 3.

The number of ‘fragmented permutations’ of size $n$ is $c_{n}/n!$ where
$(c_{n})_{n\in\mathbb{N}}$ is defined by

$(n+2)c_{n+2}=(2n+3)c_{n+1}-nc_{n},\quad c_{0}=c_{1}=1.$

It satisfies [FS09, Prop. VIII.4]

$c_{n}\sim\frac{n^{-3/4}e^{2\sqrt{n}}}{2\sqrt{e\pi}},\quad
n\rightarrow\infty.$

Here, the leading coefficient $1/2\sqrt{e\pi}$ is computed (with the rest of
the asymptotic behaviour) by exploiting a closed-form expression of the
generating function of $(c_{n}/n!)_{n\in\mathbb{N}}$. In general, this is not
available.

While we know how to compute a basis of formal asymptotic expansions that are
solutions of linear recurrences (by the results of Birkhoff-Trjitzinsky
improved by Immink [BT32, Imm84]), we do not know how to compute the leading
coefficient exactly in general. Currently, the closest we have is a certified
numerical approximation in the form of an interval that can be made
arbitrarily small, but 0 cannot be excluded. This is known as the _connexion
problem_ for linear differential equations. Still, this is a good basis for an
analytic proof of positivity, as was recently shown by Melczer and Mezzarobba
on a recurrence of order 7 with polynomial coefficients, themselves of degree
7 [MM22, DMM22].

In the case of Poincaré-type recurrences, Poincaré related the asymptotic
behaviour to the C-finite case, showing that when all the eigenvalues are
simple and of distinct moduli, any solution $(u_{n})_{n\in\mathbb{N}}$ of the
recurrence is either ultimately 0 (all its terms are 0 from a certain index
on) or satisfies $\lim u_{n+1}/u_{n}=\lambda_{i}$ for some $i$ [Poi85].
Solutions that are ultimately 0 exist if and only if the trailing coefficient
$p_{0}(n)$ of eq. 1 vanishes at a positive integer, or equivalently, when the
matrix $A(n)$ is not invertible for some $n\in\mathbb{N}$. For positivity
testing, one can proceed as for the leading coefficient: treat the initial
terms of the sequence separately up to the largest integer where this happens,
and then shift the index.

Perron, Kreuser and later Kooman gave results of a converse type: sufficient
conditions for a solution to exist with limit $u_{n+1}/u_{n}=\lambda_{i}$
[Koo91]. We rely on the following more recent analytic result, which we will
use with sequences of invertible matrices with entries in $\mathbf{Q}$.

######  Theorem 1 (Friedland [Fri06]).

Let $A(n)$ be in $\operatorname{GL}_{d}(\mathbb{C})$ for $n\in\mathbb{N}$ and
tend to a finite limit $A$ as $n\rightarrow\infty$, such that $A$ has exactly
one dominant eigenvalue $\lambda$. Then there exist two nonzero vectors $v,w$
s.t. $Av=\lambda v$ and

$\lim_{n\rightarrow\infty}\frac{A(n)\dotsm A(1)A(0)}{\|A(n)\dotsm
A(1)A(0)\|}=vw^{\mathsf{T}}.$

A vector of initial conditions $U_{0}$ is called _generic_ when
$w^{\mathsf{T}}U_{0}\neq 0$.

Thus, for a generic vector of initial conditions, the sequence $U_{n}$ has a
direction that tends to that of $v$, in a sense made more precise in section
4.

In the constant case, when $A(n)=A$ for all $n$, this theorem gives a proof of
the convergence of the classical power method [PP73]. In that situation, the
vector $w$ is a left eigenvector of $A$ for $\lambda$, i.e.,
$w^{\mathsf{T}}A=\lambda w^{\mathsf{T}}$. In the case of polynomial
coefficients, this vector $w$ is much more elusive.

######  Example 4.

The recurrence used by Apéry in his proof of the irrationality of $\zeta(3)$
[Van79] is

$(n+2)^{3}u_{n+2}=(2n+3)(17n^{2}+51n+39)u_{n+1}-(n+1)^{3}u_{n}.$

It has eigenvalues $\lambda_{\pm}=(3\pm 2\sqrt{2})^{2}$, and corresponding
eigenvectors $(1,\lambda_{\pm})^{\mathsf{T}}$. Up to a nonzero scalar, the
vector $w^{\mathsf{T}}$ is $(1,6/\zeta(3)-5).$ Since $\zeta(3)$ is irrational,
any nonzero vector of initial conditions in $\mathbb{Q}$ is generic.

In order 2, the non-generic situation is called _minimal_ as it corresponds to
a vector space of dimension 1 of solutions that do not have the dominant order
of growth. For recurrences of order 2, deciding positivity reduces to deciding
minimality [Ken+21]. Theorem 2 below generalizes this situation to arbitrary
order.

##  3\. Positivity certificates

######  Definition 3.

We say that a vector or a matrix $V$ is _positive_ (resp. non-negative), and
write $V>0$ (resp. $V\geq 0$), when all the coordinates are positive (resp.
non-negative).

Our main result is the following.

######  Theorem 2.

Let $A(n)$ be in $\operatorname{GL}_{d}(\mathbf{Q})$ for $n\in\mathbb{N}$ and
tend to a finite limit $A$ as $n\rightarrow\infty$, that has a unique simple
dominant eigenvalue and a corresponding positive eigenvector. Then proving
positivity of the solution of $U_{n+1}=A(n)U_{n}$ given $A(n)$ and $U_{0}$
reduces to deciding genericity of the initial condition $U_{0}$.

Algorithm PositivityProof in section 5 either disproves positivity or computes
a positivity certificate, in the generic situation.

If the initial condition is not generic and the sequence is positive, then,
and only then, our algorithm does not terminate. Constructing examples of
minimal-order recurrences with coefficients in $\mathbb{Q}[n]$ and initial
conditions in $\mathbb{Q}$ where this occurs does not seem to be easy.

Note that it is a consequence of Pringsheim’s theorem [Tit39] (see also
[Viv93, Had54]) that if $(u_{n})_{n\in\mathbb{N}}$ is a positive solution of
eq. 1, and $\lambda$ is a dominant eigenvalue of the limit matrix $A$, then
$|\lambda|$ itself is an eigenvalue of it. Thus if there is a unique dominant
eigenvalue $\lambda$, it is real and positive. Moreover, if $\lambda$ is an
eigenvalue of a companion matrix, then $(1,\lambda,\dots,\lambda^{d-1})$ is a
corresponding eigenvector. Thus the condition that the dominant eigenvalue has
a positive eigenvector is automatically satisfied for positive P-finite
sequences. In the matrix case, it has to be added as a hypothesis in our
approach.

###  3.1. Certificates

In theorem 2, a positivity certificate is a data-structure for a proof by
induction: it consists of a quadruple $(T,r,N,m)$ formed of an invertible
matrix $T\in\operatorname{{GL}}_{d}(\mathbb{Q})$, a rational number
$r>1\in\mathbb{Q}$ (or $r=\infty$), an integer $N\in\mathbb{N}$ and a positive
integer $m\in\mathbb{N}_{>0}$.

Verification is reduced to checking positivity of polynomials in
$\mathbf{Q}(\lambda)[n]$ for $n\geq N$, where $\lambda$ is the dominant
eigenvalue of $A$. Let $e$ be a positive eigenvector of $A$ for $\lambda$,
$v=Te$ and consider two convex cones pointed at 0. The first one is

(4) $B_{r}(v)=\\{x\in\mathbb{R}^{d}_{>0}\mid x_{i}v_{j}\leq rx_{j}v_{i}\text{
for all }i,j\\}.$

If $r=\infty$, this cone is $\mathbb{R}^{d}_{>0}$. Otherwise, it is generated
by $2^{d}-2$ vectors obtained by choosing the $i$th coordinate in
$\\{v_{i},rv_{i}\\}$ so that the result is neither $v$ nor $rv$. The second
cone is its image

$C_{r}(v)=T^{-1}B_{r}(v).$

Verification proceeds in three steps. We first present it when $m=1$:

  * _Sanity checks:_ check $\lambda>0$, $v>0$, $C_{r}(v)\in\mathbb{R}_{>0}^{d}.$

  * _Initialization:_ check that $U_{n}\geq 0$ for $n\leq N$; check that $U_{N}\in C_{r}(v)$.

  * _Induction step:_ check that $A(n)(C_{r}(v))\subset C_{r}(v)$ for $n\geq N$.

When these steps are completed, it follows that for all $n\geq N$, one has
$U_{n}\in C_{r}(v)\subset\mathbb{R}_{>0}^{d}$: positivity is proved. This
induction effectively proves $d(d-1)$ linear inequalities on
$(u_{n})_{n\in\mathbb{N}}$ simultaneously, originating in the inequalities
that define $B_{r}(v)$ (and only $d$ inequalities when $r=\infty$).

If $m>1$, the initialization also checks that $U_{N+1},\dots,U_{N+m-1}$ belong
to $C_{r}(v)$ and the induction step checks that $A(n+m-1)\dotsm
A(n)(C_{r}(v))\subset C_{r}(v)$ instead of $A(n)(C_{r}(v))\subset C_{r}(v)$.
The same argument shows that this proves positivity by induction.

In terms of algorithmic complexity, there are two expensive steps: one related
to the recurrence and another one related to the initial conditions. The
induction step can be performed by checking that each of the $2^{d}-2$ vectors
generating the cone $C_{r}(v)$ (resp. $d$ vectors when $r=\infty$) has for
image by $A(n)$ a vector of rational functions that satisfies the $d(d-1)$
inequalities (resp. $d$ inequalities) defining the cone. This amounts to
$d(d-1)(2^{d}-2)$ (resp. $d^{2}$) polynomials in $\mathbb{Q}[n]$ that have to
be proved positive for $n\geq N$ (e.g., by Sturm sequences, or simply by
certified numerical evaluation of the roots). The complexity of that step is
thus singly exponential in the order of the recurrence.

Concerning the initial conditions, checking $U_{n}\geq 0$ for $n\leq N$ has
complexity that is clearly polynomial in $N$ (one can also use multipoint
polynomial evaluation to reduce further the cost by evaluating the
coefficients $p_{i}(n)$ for $n\leq N$ efficiently); this has complexity singly
exponential in the _bit size_ of $N$. Still, at the moment we do not have an
upper bound on $N$ in terms of the input, in particular in relation to a
distance of the vector of initial conditions to the hyperplane of non-
genericity.

###  3.2. Examples of certificate verification

######  Example 5.

We start with an example where $r=+\infty$, where verification is easier.

The sequence defined by

$u_{n}:=\sum_{k=0}^{n}(-1)^{k}\frac{(4n-3k)!(4!)^{k}}{(n-k)!^{4}k!}$

is the first of a family related to a former conjecture of Gillis, Reznick and
Zeilberger [GRZ83]. Its positivity was proved automatically by Pillwein
[Pil19], using the linear recurrence of order 4 that can be computed by
Zeilberger’s algorithm:

$(2n+5)(4n+11)(4n+7)(n+4)^{3}u_{n+4}\\\
-8(4n+7)(4n+13)(n+3)(40n^{3}+380n^{2}+1193n+1240)u_{n+3}\\\
+576(192n^{6}+3072n^{5}+20108n^{4}+68918n^{3}+130513n^{2}+129613n+52815)u_{n+2}\\\
+13824(4n+15)(32n^{5}+344n^{4}+1424n^{3}+2855n^{2}+2801n+1085)u_{n+1}\\\
+331776(4n+15)(4n+11)(2n+7)(n+1)^{3}u_{n}=0$

This sequence admits a relatively small certificate of positivity:

$T=\begin{pmatrix}1&0&0&0\\\ -1&1&0&0\\\ 0&-2&1&0\\\
-3000&-1000&-40&1\end{pmatrix},\quad r=+\infty,\quad N=3,\quad m=1.$

The verification of this certificate thus consists in a proof by induction
that the following inequalities are all satisfied for $n\geq 3$:

$u_{n}>0,\quad u_{n+1}>u_{n},\quad u_{n+2}>2u_{n+1},\quad
u_{n+3}>40u_{n+1}+1000u_{n+2}+3000u_{n+3}.$

We now turn to the verification.

The characteristic polynomial has one dominant root $\lambda\approx 130.$, of
much larger modulus than the other ones. The corresponding eigenvector
$v=(1,\lambda,\lambda^{2},\lambda^{3})^{\mathsf{T}}$ is also positive. As
$T^{-1}$ is a triangular matrix with positive elements under the diagonal, we
get that $C_{r}=T^{-1}\mathbb{R}_{>0}^{d}>0$, which concludes the ‘Sanity
checks’.

Checking that the first 4 vectors $U_{0},U_{1},U_{2},U_{3}$ are positive is
done by checking $u_{i}>0$ for $i=0,\dots,6$. With
$U_{3}=(18816,1785816,177396480,18271143360)^{\mathsf{T}}$, it is easy to
check that $TU_{3}>0$, i.e., $TU_{3}\in B_{r}(v)$ or equivalently $U_{3}\in
C_{r}(v)$, concluding the initialization step.

Finally, as the cone $B_{r}$ is $\mathbb{R}_{>0}^{4}$, the induction step,
which consists in checking that
$TA_{n}T^{-1}(\mathbb{R}_{>0}^{4})\subset\mathbb{R}_{>0}^{4}$ for $n\geq 3$ is
readily achieved by a direct computation of $TA_{n}T^{-1}$, which has the form

$TA_{n}T^{-1}=\begin{pmatrix}1&1&0&0\\\ 1&1&1&0\\\ 4076&1076&38&1\\\
a_{1}(n)&a_{2}(n)&a_{3}(n)&a_{4}(n)\end{pmatrix},$

with $a_{i}(n)$ rational functions. For instance, $a_{1}(n)$ is

${\frac{8(362464n^{6}+12010912n^{5}+121406462n^{4}+567578151n^{3}+1363921108n^{2}+1636882352n+779476880)}{(32n^{6}+608n^{5}+4738n^{4}+19353n^{3}+43628n^{2}+51376n+24640)}}$

making its positivity apparent. The same is true for the other ones. Therefore
the image of any vector with positive coordinates also has positive
coordinates.

######  Example 6.

As an example with a finite $r$, we consider the sequence
$(u_{n})_{n\in\mathbb{N}}$ defined by the third-order recurrence

$(n+1)u_{n+3}=\left(\frac{77}{30}n+2\right)u_{n+2}-\left(\frac{13}{6}n-3\right)u_{n+1}+\left(\frac{3}{5}n+2\right)u_{n},\qquad
n\in\mathbb{N},$

with initial conditions $u_{0}=1$, $u_{1}=15/14$, $u_{2}=8/7$. This is a
recurrence that falls outside of the domain reachable by the methods of Kauers
and Pillwein [KP10, Pil19]. Here is a certificate for its positivity:

$T=\begin{pmatrix}-36/7&76/7&-33/7\\\ 162/7&-405/7&250/7\\\
303/14&-4783/84&3049/84\end{pmatrix},\quad r=5/3,\quad N=3040,\quad m=1.$

The dominant eigenvalue is $\lambda=1$ and the vector $v$ is
$(1,1,1)^{\mathsf{T}}$. So the first part of the ‘Sanity checks’ is easy. The
$2^{d}-2=6$ edge vectors of the cone $B_{r}(v)$ are

$\begin{pmatrix}r\\\ 1\\\ 1\end{pmatrix},\quad\begin{pmatrix}1\\\ r\\\
1\end{pmatrix},\quad\begin{pmatrix}1\\\ 1\\\
r\end{pmatrix},\quad\begin{pmatrix}r\\\ r\\\
1\end{pmatrix},\quad\begin{pmatrix}1\\\ r\\\
r\end{pmatrix},\quad\begin{pmatrix}r\\\ 1\\\ r\end{pmatrix},\quad\text{with
$r=5/3$}.$

In order to check that $C_{r}(v)\subset\mathbb{R}^{d}_{>0}$, it is sufficient
to test that $T^{-1}V>0$ for each of these vectors, concluding the ‘Sanity
checks’.

For the initialization, one checks the positivity of the first $N$ terms of
the sequence and that $TU_{N}$ satisfies the $d(d-1)=6$ inequalities that
define $B_{r}(v)$.

Finally, for the induction step, for each generator $G$ of the cone
$B_{r}(v)$, one checks that the vector of polynomials $TA(n)T^{-1}G$ satisfies
the linear inequalities that define $B_{r}(v)$. For instance, for the
generator $G_{1}=\begin{pmatrix}r&1&1\end{pmatrix}^{\mathsf{T}}$ one gets the
polynomials

$360612n+392450160,1939140n-264007440,1247967n+399271660,\\\
1406727n-268100340,1839915n+153100060,420147n+142185660,$

that have to be proved positive for $n\geq N$. As they are all linear in $n$
in this example, this is straightforward.

In terms of the sequence $(u_{n})_{n\in\mathbb{N}}$, this proof shows by
induction that for $n\geq n_{0}$, the following six inequalities are satisfied

$\displaystyle 0$ $\displaystyle<-666u_{n}+1595u_{n+1}-915u_{n+2},$
$\displaystyle\quad 0$ $\displaystyle<918u_{n}-2253u_{n+1}+1349u_{n+2},$
$\displaystyle 0$ $\displaystyle<-2538u_{n}+6303u_{n+1}-3709u_{n+2},$
$\displaystyle\quad 0$ $\displaystyle<3258u_{n}-9335u_{n+1}+6245u_{n+2},$
$\displaystyle 0$ $\displaystyle<1422u_{n}-3317u_{n+1}+1951u_{n+2},$
$\displaystyle\quad 0$ $\displaystyle<10386u_{n}-26651u_{n+1}+16433u_{n+2}.$

##  4\. Convergent Contractions

The geometric insight on the convergence in Friedland’s theorem makes use of
Hilbert’s pseudo-metric.

######  Definition 4.

Hilbert’s pseudo-metric on $\mathbb{R}_{>0}^{d}$ is defined by

$d_{H}(x,y)=\log\frac{\max_{i}(x_{i}/y_{i})}{\min_{i}(x_{i}/y_{i})}.$

Being a pseudo-metric means that: $d_{H}(x,x)=0$; $d_{H}(x,y)=d_{H}(y,x)$ and
$d_{H}(x,y)\leq d_{H}(x,z)+d_{H}(y,z).$ All are easy to check. Moreover,
$d_{H}(x,y)=0$ if and only if there exists $\mu>0$ such that $y=\mu x$.

For this pseudo-metric, the open ball centered at $v$ and of radius $\log r$
is the cone $B_{r}(v)$ from eq. 4.

######  Theorem 3 (Birkhoff [Bir57]).

For a positive matrix $A\in\mathbb{R}_{>0}^{d\times d}$, let
$L(A)=\sup_{x\neq\alpha y}d_{H}(Ax,Ay)/d_{H}(x,y)$. Then

$L(A)=\frac{1-\sqrt{\psi(A)}}{1+\sqrt{\psi(A)}}\quad\text{with}\quad\psi(A)=\min_{i,j,k,\ell}\frac{a_{ik}a_{j\ell}}{a_{i\ell}a_{jk}},$

showing that $L$ is continuous and that $A$ is a contraction.

This was used by Birkhoff to give a new proof of Perron’s result that any
positive matrix admits a unique positive eigenvector (and a generalization in
arbitrary dimension).

The key result for our method is the following theorem at the heart of
Friedland’s proof, that we make explicit for later use.

######  Theorem 4.

If $A(n)>0$ tends to $A>0$, let $v>0$ be such that $Av=\lambda v$ (which
exists by Perron’s theorem), then for $n$ sufficiently large,
$A(n)(B_{r}(v))\subset B_{r}(v)$.

###### Proof.

Let $x\in B_{r}(v)$, then

$\displaystyle d_{H}(A(n)x,v)$ $\displaystyle\leq
d_{H}(A(n)x,A(n)v)+d_{H}(A(n)v,v)$ $\displaystyle\leq L(A(n))\log
r+d_{H}(A(n)v,Av).$

The first summand tends to $L(A)\log r<\log r$, the second one to 0, so the
sum is smaller than $\log r$ for $n$ sufficiently large, i.e., $A_{n}(x)\in
B_{r}(v).$ ∎

Reduction to the positive case is achieved by the following.

######  Lemma 1 (Friedland).

For a matrix $A\in\mathbf{Q}^{d\times d}$ with a simple dominant eigenvalue
$\lambda>0$, there exists $T\in\operatorname{GL}_{d}(\mathbb{Q})$ such that
$TAT^{-1}$ has positive right and left eigenvectors $a,b$ for $\lambda$.

Then $TA^{m}T^{-1}/\lambda^{m}$ tends to $ab^{\mathsf{T}}$ (by theorem 1) and
thus has to be positive for some finite $m$.

###### Proof.

Friedland’s proof of the lemma is constructive (and leaves a lot of freedom in
the construction of $T$). We reproduce it here to make the algorithmic part of
this work self-contained.

Let $\lambda$ be the dominant eigenvalue of $A$. There exists
$Q\in\operatorname{GL}_{d}(\mathbf{Q}(\lambda))$ such that
$B=QAQ^{-1}=(\lambda)\oplus B^{\prime}$ for some
$B^{\prime}\in\mathbf{Q}(\lambda)^{(d-1)\times(d-1)}$. If $e_{1}$ denotes the
vector $(1,0,\dots,0)^{\mathsf{T}}$, then $Be_{1}=B^{\mathsf{T}}e_{1}=\lambda
e_{1}$. Choose $a=(1,\dots,1)^{\mathsf{T}}$ and $b$ a positive vector with
coordinates in $\mathbb{Q}$ such that $a^{\mathsf{T}}b=1$. Let
$(s_{2},\dots,s_{d})$ be a basis of vectors, all in $\mathbb{Q}^{d}$ and
orthogonal to $b$ and form $S\in\mathbb{Q}^{d\times d}$, the matrix with
columns $(a,s_{2},\dots,s_{d})$ so that $Se_{1}=a$ and
$S^{\mathsf{T}}b=e_{1}$. Let next $T=SQ$ and $M=TAT^{-1}$. Then,

$\displaystyle Ma$ $\displaystyle=SBS^{-1}a=SBe_{1}=\lambda Se_{1}=\lambda a,$
$\displaystyle M^{\mathsf{T}}b$
$\displaystyle=(S^{-1})^{\mathsf{T}}B^{\mathsf{T}}S^{\mathsf{T}}b=(S^{-1})^{\mathsf{T}}B^{\mathsf{T}}e_{1}=\lambda(S^{-1})^{\mathsf{T}}e_{1}=\lambda
b.$

By continuity and density of $\mathbb{Q}$, one can further restrict to
$T\in\operatorname{GL}_{d}(\mathbb{Q})$. ∎

##  5\. Algorithm and Proof

Input : A recurrence of Poincaré type, in the form of a matrix
$A(n)\in\mathbf{Q}(n)^{d\times d}$; a vector $U_{0}\in\mathbf{Q}^{d}$ of
initial conditions. It is assumed that $A=\lim_{n\rightarrow\infty}$ has a
unique simple dominant eigenvalue $\lambda$ with eigenvector $e>0$. (This can
be checked.)

Output : One of (Positive,$T,r,N,m$), (Non-positive)

1 if  _$\lambda <0$_ then return (Non-positive);

2 Find $T\in\mathrm{GL}_{d}(\mathbb{Q})$ and $m>0\in\mathbb{N}$ such that
$TA^{m}T^{-1}>0$ ;

3 $v\leftarrow T{e}$; if  _$v <0$_ then $T\leftarrow-T$, $v\leftarrow-v$ ;

4 Find $r>1$ such that $T^{-1}(B_{r}(v))>0$ // $B_{r}(v)$ from eq. 4;

5 Find $K\geq 0\in\mathbb{N}$ such that $n\geq K\Rightarrow TA({n+m-1})\dotsm
A({n})T^{-1}(B_{r}(v))\subset B_{r}(v)$;

6 for  _$i=0,\dots,K$_ do

7 if  _$U_{i}\not\geq 0$_ then return (Non-positive);

8

9for  _$i=K,K+1,\dots,\infty$_ do

10 if  _$U_{i}\not\geq 0$_ then return (Non-positive);

11 if  _$TU_{j}\in B_{r}(v)$ for $j=K,\dots,K+m-1$_ then

12 return (Positive,$T,m,r,i$)

Algorithm 1 PositivityProof

Algorithm PositivityProof is a direct consequence of the results of the
previous section. We now prove its correctness, thereby proving theorem 2.

By Friedland’s theorem, the direction of $U(n)$ tends to that of the
eigenvector corresponding to the unique dominant eigenvalue $\lambda$ of $A$,
which, being unique, is real. If $\lambda$ is negative, then for sufficiently
large $n$, one of $U(n)$ and $A(n)U(n)$ has a negative coordinate (by
Pringsheim’s theorem). This is checked by step 1.

The next step is to compute a $T\in\operatorname{GL}_{d}(\mathbb{Q})$ and an
integer $m>0$ such that $TA^{m}T^{-1}>0$. This is possible by lemma 1.

Next, by definition of $e$ and $v$, $TA^{m}T^{-1}v=\lambda^{m}v$. So $v$ is an
eigenvector for the positive eigenvalue of a positive matrix. By Perron’s
theorem, it is a real multiple of a positive vector. Thus either $v>0$ or
$v<0$ and then changing $T$ into $-T$ and $v$ into $-v$ turns $v$ into a
positive eigenvector of $TA^{m}T^{-1}.$ This is what is done in step 3.

Since $e=T^{-1}v>0$, by continuity of the linear map $T^{-1}$, there exists a
small enough ball $B_{r}(v)$ around $v$ such that $T^{-1}B_{r}(v)>0$. This can
be computed for instance by starting from $r=2$ and using dichotomy to divide
the distance between $r$ and $1$ until an appropriate $r$ is found. This
proves that step 4 succeeds.

By theorem 4 applied to $TA(n+m-1)\dotsm A(n)T^{-1}$, there exists a $K$ as
required by step 5. In order to compute it, one can compute $TA({n+m})\dots
A(n)T^{-1}G$ for each generator $G$ of the cone $B_{r}(v)$, which gives a
vector of polynomials in $\mathbf{Q}(\lambda)[n]$ that has to be ultimately
positive by the existence of $K$. For instance, for each polynomial, one can
start from $i=1$ and check whether the polynomial is positive on $[i,\infty)$
using Sturm sequences, and if not, double $i$. In the end, $K$ can be taken as
the maximum of the values obtained for each coordinate for each generator $G$.
This proves that step 5 succeeds.

Step 6 consists simply in checking that the initial values up to $K$ are
nonnegative.

Finally, steps 8–11 rely on Friedland’s theorem 1 which shows that for any
generic vector of initial conditions, the direction of $U_{n}$ tends to that
of $e$ and therefore $d_{H}(TU_{n},v)\rightarrow 0$ as $n\rightarrow\infty$.
Thus for large enough $j$, all $TU_{j}$ belong to $B_{r}(v)$, showing that the
seemingly infinite loop always terminates for generic initial conditions and
concluding the proof.

### Example

For the sequence $(s_{n})_{n\in\mathbb{N}}$ from eq. 2 in the introduction,
denoting by $\mathrm{S}(n)$ the vector $(s_{n},s_{n+1})^{\mathsf{T}}$, the
recurrence is $\mathrm{S}_{n+1}=A(n)\mathrm{S}_{n}$ with

$A(n)=\begin{pmatrix}0&1\\\
\frac{-81(3n+2)(3n+4)}{2(n+2)^{2}}&\frac{(81n^{2}+243n+186)}{2(n+2)^{2}}\end{pmatrix}\qquad\text{and}\qquad\mathrm{S}_{0}=\begin{pmatrix}1\\\
12\end{pmatrix}.$

The limit matrix $A$ of $A(n)$ has one simple dominant eigenvalue
$\lambda=27>0$ with $e=(1,\lambda)$ its associated eigenvector. We follow the
steps of the algorithm.

First, following the steps in the proof of lemma 1, a possible choice of
matrix is

$T=\frac{1}{13}\begin{pmatrix}-14&1\\\ 1&0\end{pmatrix}.$

Since $TAT^{-1}>0$, we have $m=1$ and note that the vector $v=Te=(1,1)>0$.

Next, as the inverse of $T$ is triangular with positive elements under the
anti-diagonal, for all real $r>0$, $T^{-1}B_{r}(v)>0$, showing that we can
take $r=+\infty$. In Step 5, $K$ can be chosen as the rank for which the
matrix $TA(n)T^{-1}$ becomes positive. The value of this matrix is

$\begin{pmatrix}\frac{53n^{2}+131n+74}{2(n+1)^{2}}&\frac{13n^{2}+376n+388}{26(n+1)^{2}}\\\
13&14\end{pmatrix}$

showing that $K=0$ works. After checking that $U_{0}$, $U_{1}$ and $TU_{1}$
are positive, the positivity is concluded and the final step of the algorithm
finds $N=1$.

Note that this choice of matrix $T$ means that the algorithm proves the
positivity of $(s_{n})_{n\in\mathbb{N}}$ by synthesizing and proving the
inequalities

$s_{n+1}>14s_{n}>0$

for $n\geq 1$. In this example, this recovers the stragegy of Kauers and
Pillwein [KP10] of looking for an inequality $u_{n+1}\geq\mu u_{n}$. One way
of seeing the improvement brought by our algorithm is that it will always
succeed in producing a matrix $T$ when the conditions of theorem 2 are met,
while the inequalities $u_{n+1}\geq\mu u_{n}$ correspond to a restricted set
of matrices.

##  6\. Conclusion

Informally speaking, this work consists in providing certificates for a large
class of P-finite sequences, whose positivity follows ‘in an easy way’ from
its asymptotic behaviour. These certificates can be viewed as a finite set of
linear inequalities satisfied by the shifted sequences
$(u_{n+k})_{n\in\mathbb{N}}$, whose simultaneous proof by induction implies
the positivity of $(u_{n})_{n\in\mathbb{N}}$ and reduces to checking the
positivity of a finite number of univariate polynomials.

The constraint that the matrix $A$ in theorem 2 has a unique dominant
eigenvalue that is simple is a limitation of our approach. For instance, the
sequence proved positive by Melczer and Mezzarobba [MM22] has a dominant
eigenvalue that is double and thus inaccessible by the approach presented
here. Work is in progress to extend our approach to situations of this type
and to improve the choice of change of basis $T$, that has a strong impact on
the value of the number $N$ of terms that has to be tested positive.

#### Acknowledgements.

Alin Bostan and Mohab Safey El Din made many very useful suggestions on
previous versions of this article. The presentation also benefited from the
feedback of the participants to the workshop _Algorithmic Aspects of Dynamical
Systems_ at McGill University’s Bellairs Research Institute.

This work has been supported in part by the ANR project NuSCAP
ANR-20-CE48-0014.

## References

  * [Alm+22] Shaull Almagor, Dmitry Chistikov, Joël Ouaknine and James Worrell  “O-minimal invariants for discrete-time dynamical systems”  In _ACM Trans. Comput. Log._ 23.2, 2022, pp. Art. 920  DOI: 10.1145/3501299
  * [BPR08] Saugata Basu, Richard Pollack and Marie-Françoise Roy  “Algorithms in Real Algebraic Geometry”  Springer-Verlag, 2008
  * [Bir57] Garrett Birkhoff  “Extensions of Jentzsch’s theorem”  In _Trans. Amer. Math. Soc._ 85, 1957, pp. 219–227  DOI: 10.2307/1992971
  * [BT32] George D. Birkhoff and W.. Trjitzinsky  “Analytic Theory of Singular Difference Equations”  In _Acta Mathematica_ 60, 1932, pp. 1–89
  * [Bol+14] Sylvie Boldo et al.  “Trusting computations: a mechanized proof from partial differential equations to actual program”  In _Comput. Math. Appl._ 68.3, 2014, pp. 325–352  DOI: 10.1016/j.camwa.2014.06.004
  * [Bug+22] Yann Bugeaud et al.  “Absolute root separation”  In _Experimental Mathematics_ 31.3, 2022, pp. 805–812  DOI: 10.1080/10586458.2019.1699480
  * [Col75] George E Collins  “Quantifier elimination for real closed fields by cylindrical algebraic decompostion”  In _Automata Theory and Formal Languages: 2nd GI Conference Kaiserslautern, May 20–23, 1975_ , 1975, pp. 134–183  Springer
  * [DMM22] Ruiwen Dong, Stephen Melczer and Marc Mezzarobba  “Computing error bounds for asymptotic expansions of regular P-recursive sequences”, 2022  URL: https://arxiv.org/pdf/2212.11742.pdf
  * [FS09] Philippe Flajolet and Robert Sedgewick  “Analytic Combinatorics”  Cambridge University Press, 2009
  * [Fri06] Shmuel Friedland  “Convergence of products of matrices in projective spaces”  In _Linear Algebra Appl._ 413.2-3, 2006, pp. 247–263  DOI: 10.1016/j.laa.2004.06.021
  * [GK05] Stefan Gerhold and Manuel Kauers  “A procedure for proving special function inequalities involving a discrete parameter”  In _Proceedings of the 2005 international symposium on Symbolic and algebraic computation - ISSAC ’05_ , 2005  DOI: 10.1145/1073884.1073907
  * [GK06] Stefan Gerhold and Manuel Kauers  “A computer proof of Turán’s inequality”  In _Journal of Inequalities in Pure and Applied Mathematics_ 7.2, 2006, pp. Article 42  URL: http://jipam.vu.edu.au/images/282_05_JIPAM/282_05.pdf
  * [GRZ83] Joseph Gillis, Bruce Reznick and Doron Zeilberger  “On elementary methods in positivity theory”  In _SIAM Journal on Mathematical Analysis_ 14.2 SIAM, 1983, pp. 396–398
  * [GS96] Xavier Gourdon and Bruno Salvy  “Effective asymptotics of linear recurrences with rational coefficients”  In _Discrete Mathematics_ 153.1–3, 1996, pp. 145–163  DOI: 10.1016/0012-365X(95)00133-H
  * [Had54] Jacques Hadamard  “History of science and psychology of invention”  In _Mathematika_ 1, 1954, pp. 1–3  DOI: 10.1112/S0025579300000450
  * [HHH06] Vesa Halava, Tero Harju and Mika Hirvensalo  “Positivity of second order linear recurrent sequences”  In _Discrete Appl. Math._ 154.3, 2006, pp. 447–451  DOI: 10.1016/j.dam.2005.10.009
  * [HJK17] Andreas Humenberger, Maximilian Jaroschek and Laura Kovács  “Automated generation of non-linear loop invariants utilizing hypergeometric sequences”  In _ISSAC’17—Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation_ ACM, New York, 2017, pp. 221–228
  * [HJK18] Andreas Humenberger, Maximilian Jaroschek and Laura Kovács  “Invariant generation for multi-path loops with polynomial assignments”  In _Verification, model checking, and abstract interpretation_ 10747, Lecture Notes in Comput. Sci.  Springer, Cham, 2018, pp. 226–246
  * [Imm84] Geertrui K. Immink  “Asymptotics of analytic difference equations” 1085, Lecture Notes in Mathematics  Springer-Verlag, Berlin, 1984
  * [Kau06] Manuel Kauers  “Shift equivalence of P-finite sequences”  In _Electron. J. Combin._ 13.1, 2006, pp. Research Paper 10016 pp. (electronic)  URL: http://www.combinatorics.org/Volume_13/Abstracts/v13i1r100.html
  * [KP10] Manuel Kauers and Veronika Pillwein  “When can we detect that a P-finite sequence is positive?”  In _ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation_ ACM, New York, 2010, pp. 195–201  DOI: 10.1145/1837934.1837974
  * [Ken+21] George Kenison et al.  “On positivity and minimality for second-order holonomic sequences”  In _46th International Symposium on Mathematical Foundations of Computer Science_ 202, LIPIcs. Leibniz Int. Proc. Inform.  Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, pp. Art. No. 6715
  * [Ken+23] George Kenison, Joris Nieuwveld, Joël Ouaknine and James Worrell  “Positivity problems for reversible linear recurrence sequences”, 2023
  * [Koo91] Robert-Jan Kooman  “Convergence properties of recurrence sequences” 83, CWI Tract  Stichting Mathematisch Centrum, Centrum voor Wiskunde en Informatica, Amsterdam, 1991
  * [Lip+22] Richard Lipton et al.  “On the Skolem problem and the Skolem conjecture”  In _Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science_ ACM, New York, 2022, pp. Article 59  DOI: 10.1145/3531130.3533328
  * [MM22] Stephen Melczer and Marc Mezzarobba  “Sequence positivity through numeric analytic continuation: uniqueness of the Canham model for biomembranes”  In _Comb. Theory_ 2.2, 2022, pp. Paper No. 420  DOI: 10.5070/C62257847
  * [MS10] Marc Mezzarobba and Bruno Salvy  “Effective Bounds for P-Recursive Sequences”  In _Journal of Symbolic Computation_ 45.10, 2010, pp. 1075–1096  DOI: 10.1016/j.jsc.2010.06.024
  * [Mig92] Maurice Mignotte  “Mathematics for Computer Algebra”  Springer New York, 1992
  * [OW14] Joël Ouaknine and James Worrell  “On the positivity problem for simple linear recurrence sequences”  In _Automata, languages, and programming. Part II_ 8573, Lecture Notes in Comput. Sci.  Springer, Heidelberg, 2014, pp. 318–329
  * [OW14a] Joël Ouaknine and James Worrell  “Positivity problems for low-order linear recurrence sequences”  In _Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms_ ACM, New York, 2014, pp. 366–379  DOI: 10.1137/1.9781611973402.27
  * [PP73] Beresford N. Parlett and William G. Poole  “A geometric theory for the ${\rm QR},\,{\rm LU}$ and power iterations”  In _SIAM J. Numer. Anal._ 10, 1973, pp. 389–412  DOI: 10.1137/0710035
  * [PWW23] Yanni Pei, Yaling Wang and Yi Wang  “Positivity problem of three-term recurrence sequences”, 2023
  * [PWZ96] Marko Petkovšek, Herbert S. Wilf and Doron Zeilberger  “${A}={B}$”  Wellesley, MA: A. K. Peters, 1996
  * [Pil08] Veronika Pillwein  “Positivity of certain sums over Jacobi kernel polynomials”  In _Advances in Applied Mathematics_ 41.3, 2008, pp. 365–377  DOI: 10.1016/j.aam.2007.12.001
  * [Pil13] Veronika Pillwein  “Termination conditions for positivity proving procedures”  In _ISSAC 2013—Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation_ ACM, New York, 2013, pp. 315–321  DOI: 10.1145/2465506.2465945
  * [Pil19] Veronika Pillwein  “On the positivity of the Gillis-Reznick-Zeilberger rational function”  In _Adv. in Appl. Math._ 104, 2019, pp. 75–84  DOI: 10.1016/j.aam.2018.11.003
  * [Poi85] Henri Poincaré  “Sur les équations linéaires aux différentielles ordinaires et aux différences finies.”  In _American Journal of Mathematics_ 7.3, 1885, pp. 203–258
  * [SS14] Alexander D. Scott and Alan D. Sokal  “Complete monotonicity for inverse powers of some combinatorially defined polynomials”  In _Acta Math._ 213.2, 2014, pp. 323–392  DOI: 10.1007/s11511-014-0121-6
  * [Ser+16] Romain Serra et al.  “Fast and accurate computation of orbital collision probability for short-term encounters”  In _Journal of Guidance, Control, and Dynamics_ 39.5, 2016, pp. 1009–1021  DOI: 10.2514/1.G001353
  * [Sta80] Richard P. Stanley  “Differentiably Finite Power Series”  In _European Journal of Combinatorics_ 1.2, 1980, pp. 175–188
  * [Sta99] Richard P. Stanley  “Enumerative combinatorics”  Cambridge University Press, 1999
  * [SZ15] Armin Straub and Wadim Zudilin  “Positivity of rational functions and their diagonals”  In _J. Approx. Theory_ 195, 2015, pp. 57–69  DOI: 10.1016/j.jat.2014.05.012
  * [Tit39] Edward C. Titchmarsh  “The Theory of Functions”  Oxford University Press, 1939
  * [Van79] Alfred Van der Poorten  “A Proof that Euler missed $\ldots$ Apéry’s Proof of The Irrationality of $\zeta(3)$”  In _Mathematical Intelligencer_ 1, 1979, pp. 195–203
  * [Viv93] G. Vivanti  “Sulle serie di potenze”  In _Rivista di Matematica_ 3, 1893, pp. 111–114
  * [Yap00] Chee Keng Yap  “Fundamental Problems in Algorithmic Algebra”  New York: Oxford University Press, 2000
  * [Zei90] Doron Zeilberger  “A holonomic systems approach to special functions identities”  In _Journal of Computational and Applied Mathematics_ 32.3, 1990, pp. 321–368