Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Constant-recursive sequence
Summary
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.