Constant-recursive sequence

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, an <a href="/facts/Sequence/gV2S4uqp">infinite sequence</a> of <a href="/facts/Number/auQSAE2m">numbers</a> 
 
 
 
 
 s
 
 0
 
 
 ,
 
 s
 
 1
 
 
 ,
 
 s
 
 2
 
 
 ,
 
 s
 
 3
 
 
 ,
 …
 
 
 {\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots }
 
 is called constant-recursive if it satisfies an equation of the form

s
          
            n
          
        
        =
        
          c
          
            1
          
        
        
          s
          
            n
            −
            1
          
        
        +
        
          c
          
            2
          
        
        
          s
          
            n
            −
            2
          
        
        +
        ⋯
        +
        
          c
          
            d
          
        
        
          s
          
            n
            −
            d
          
        
        ,
      
    
    {\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d},}

for all 
 
 
 
 n
 ≥
 d
 
 
 {\displaystyle n\geq d}
 
, where 
 
 
 
 
 c
 
 i
 
 
 
 
 {\displaystyle c_{i}}
 
 are <a href="/facts/Constant_(mathematics)/SxlxTWFT">constants</a>. The equation is called a <a href="/facts/Linear_recurrence_with_constant_coefficients/gs9PR0D7">linear recurrence relation</a>.
The concept is also known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, or a C-finite sequence.
For example, the <a href="/facts/Fibonacci_sequence/mqxpAUQD">Fibonacci sequence</a>

0
 ,
 1
 ,
 1
 ,
 2
 ,
 3
 ,
 5
 ,
 8
 ,
 13
 ,
 …
 
 
 {\displaystyle 0,1,1,2,3,5,8,13,\ldots }
 
,
is constant-recursive because it satisfies the linear recurrence 
 
 
 
 
 F
 
 n
 
 
 =
 
 F
 
 n
 −
 1
 
 
 +
 
 F
 
 n
 −
 2
 
 
 
 
 {\displaystyle F_{n}=F_{n-1}+F_{n-2}}
 
: each number in the sequence is the sum of the previous two. 
Other examples include the <a href="/facts/Power_of_two/MA6WEpTt">power of two</a> sequence 
 
 
 
 1
 ,
 2
 ,
 4
 ,
 8
 ,
 16
 ,
 …
 
 
 {\displaystyle 1,2,4,8,16,\ldots }
 
, where each number is the sum of twice the previous number, and the <a href="/facts/Square_number/jfakASPK">square number</a> sequence 
 
 
 
 0
 ,
 1
 ,
 4
 ,
 9
 ,
 16
 ,
 25
 ,
 …
 
 
 {\displaystyle 0,1,4,9,16,25,\ldots }
 
. All <a href="/facts/Arithmetic_progression/c4ew9Xoq">arithmetic progressions</a>, all <a href="/facts/Geometric_progression/SVrkRHDX">geometric progressions</a>, and all <a href="/facts/Polynomial/Lzak8VVx">polynomials</a> are constant-recursive. However, not all sequences are constant-recursive; for example, the <a href="/facts/Factorial/kkfy1Bwe">factorial</a> sequence 
 
 
 
 1
 ,
 1
 ,
 2
 ,
 6
 ,
 24
 ,
 120
 ,
 …
 
 
 {\displaystyle 1,1,2,6,24,120,\ldots }
 
 is not constant-recursive.
Constant-recursive sequences are studied in <a href="/facts/Combinatorics/k14xUoKT">combinatorics</a> and the theory of <a href="/facts/Finite_difference/aY1txFhj">finite differences</a>. They also arise in <a href="/facts/Algebraic_number_theory/LPzDT5CA">algebraic number theory</a>, due to the relation of the sequence to <a href="/facts/Polynomial_root/mlK3dhoT">polynomial roots</a>; in the <a href="/facts/Analysis_of_algorithms/pStoBgBn">analysis of algorithms</a>, as the running time of simple <a href="/facts/Recursion_(computer_science)/2uXo18Gv">recursive functions</a>; and in the theory of <a href="/facts/Formal_language/crDTyP8q">formal languages</a>, where they count strings up to a given length in a <a href="/facts/Regular_language/ahxw67T1">regular language</a>. Constant-recursive sequences are <a href="/facts/Closure_(mathematics)/Ct6r2fJz">closed</a> under important mathematical operations such as <a href="/facts/Pointwise/dt4Mrs6w">term-wise</a> <a href="/facts/Addition/apFWJBFB">addition</a>, term-wise <a href="/facts/Multiplication/VtcUjpNv">multiplication</a>, and <a href="/facts/Cauchy_product/UF8fbLwg">Cauchy product</a>.
The <a href="/facts/Skolem%E2%80%93Mahler%E2%80%93Lech_theorem/x75nCBfz">Skolem–Mahler–Lech theorem</a> states that the <a href="/facts/Zero_of_a_function/mlK3dhoT">zeros</a> of a constant-recursive sequence have a regularly repeating (eventually periodic) form. The <a href="/facts/Skolem_problem/cMWS80o8">Skolem problem</a>, which asks for an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> to determine whether a linear recurrence has at least one zero, is an <a href="/facts/List_of_unsolved_problems_in_mathematics/RroxGPpP">unsolved problem in mathematics</a>.

Constant-recursive sequence open-in-new

Constant-recursive sequence