Constant-recursive sequence

In mathematics, an infinite sequence of numbers ${\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots }$ is called constant-recursive if it satisfies an equation of the form

$${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d},}$$

for all ${\displaystyle n\geq d}$, where ${\displaystyle c_{i}}$ are constants. The equation is called a linear recurrence relation. The concept is also known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, or a C-finite sequence.^[1]

For example, the Fibonacci sequence

${\displaystyle 0,1,1,2,3,5,8,13,\ldots }$,

is constant-recursive because it satisfies the linear recurrence ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$: each number in the sequence is the sum of the previous two.^[2] Other examples include the power of two sequence ${\displaystyle 1,2,4,8,16,\ldots }$, where each number is the sum of twice the previous number, and the square number sequence ${\displaystyle 0,1,4,9,16,25,\ldots }$. All arithmetic progressions, all geometric progressions, and all polynomials are constant-recursive. However, not all sequences are constant-recursive; for example, the factorial sequence ${\displaystyle 1,1,2,6,24,120,\ldots }$ is not constant-recursive.

Constant-recursive sequences are studied in combinatorics and the theory of finite differences. They also arise in algebraic number theory, due to the relation of the sequence to polynomial roots; in the analysis of algorithms, as the running time of simple recursive functions; and in the theory of formal languages, where they count strings up to a given length in a regular language. Constant-recursive sequences are closed under important mathematical operations such as term-wise addition, term-wise multiplication, and Cauchy product.

The Skolem–Mahler–Lech theorem states that the zeros of a constant-recursive sequence have a regularly repeating (eventually periodic) form. The Skolem problem, which asks for an algorithm to determine whether a linear recurrence has at least one zero, is an unsolved problem in mathematics.