Positivity problem for linear recurrences

Start with 0 and 1. Make each next number by doubling the latest number and subtracting the one before it. This gives 0, 1, 2, 3, 4, and so on; here every number is nonnegative.

For any rule of this kind, with fixed integer weights and finitely many starting integers, can a program always decide whether every number it will ever produce is nonnegative? Checking a long initial list alone does not answer a question about all future steps.[1]

Can a finite algorithm always determine whether a fixed integer update rule ever produces a negative number, including at the start? Consider $u_0=0$, $u_1=1$ and $u_{n+2}=2u_{n+1}-u_n$. Its terms are $0,1,2,3,4,\ldots$; substitution shows $u_n=n$ satisfies the rule.

A linear recurrence uses fixed coefficients to combine a bounded number of previous terms. The recurrence order is the smallest number of preceding positions needed in such a relation. The input here has integer coefficients and initial values, with no fixed bound on order. Positivity requires $u_n\ge0$ for every $n\ge0$, not merely for all sufficiently late terms.[1] [2]

No decision method is known for arbitrary order.[2]

Low-order and other restricted families have decision procedures, but those restrictions do not yield a procedure for arbitrary order. For a simple recurrence, the polynomial determined by its coefficients has no repeated roots: values at which that polynomial is zero. Even in that restricted family, deciding that every term is nonnegative remains open in general.

Ultimate Positivity asks whether the terms are nonnegative from some point onward, and it is decidable for simple recurrences. The distinction is visible with starting values $-1,0$ under the same doubling-and-subtraction rule: the terms are $-1,0,1,2,\ldots$. They are eventually nonnegative but fail Positivity because of the first term.[2]

A program can repeatedly update numbers by a fixed linear rule and continue only while a chosen quantity stays nonnegative. Knowing whether that quantity ever becomes negative can decide whether this particular loop stops. The question connects a compact arithmetic rule with the behavior of an unbounded computation.[1] [2]

Linear recurrence values can be represented by repeated multiplication of a fixed matrix, followed by reading a linear combination of its coordinates. This places the sign question inside finite-dimensional linear dynamics.

For a loop that uses the corresponding updates and continues while that readout is nonnegative, a negative term marks a stopping step; nonnegativity forever keeps it running. The connection concerns this specific form of loop, not all programs. It gives the infinite sign condition a concrete computational role while exposing how hard it can be to turn linear structure into a terminating verification method.[1] [2]