Constant-recursive sequence

In mathematics and theoretical computer science, a constant-recursive sequence is an infinite sequence of numbers where each number in the sequence is equal to a fixed linear combination of one or more of its immediate predecessors. A constant-recursive sequence is also known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, a C-finite sequence, or a solution to a linear recurrence with constant coefficients. The most famous example of a constant-recursive sequence is the Fibonacci sequence , in which each number is the sum of the previous two. The power of two sequence is also constant-recursive because each number is the sum of twice the previous number. The square number sequence is also constant-recursive. However, not all sequences are constant-recursive; for example, the factorial sequence is not constant-recursive. All arithmetic progressions, all geometric progressions, and all polynomials are constant-recursive. Formally, a sequence of numbers is constant-recursive if it satisfies a recurrence relation where are constants. For example, the Fibonacci sequence satisfies the recurrence relation where is the th Fibonacci number. 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 the roots of a polynomial; in the analysis of algorithms as the running time of simple recursive functions; and in formal language theory, 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. On the other hand, the Skolem problem, which asks for an algorithm to determine whether a linear recurrence has at least one zero, is a famous unsolved problem in mathematics.