k-regular sequence

<h2 id="definition">Definition</h2>
There exist several characterizations of k-regular sequences, all of which are equivalent. Some common characterizations are as follows. For each, we take R′ to be a <a href="/facts/Commutative/WaYxJLxd">commutative</a> <a href="/facts/Noetherian_ring/kYbRSdnp">Noetherian ring</a> and we take R to be a <a href="/facts/Ring_(mathematics)/JnCUXz63">ring</a> containing R′.

<h3>k-kernel</h3>
Let k ≥ 2. The k-kernel of the sequence 
 
 
 
 s
 (
 n
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle s(n)_{n\geq 0}}
 
 is the set of subsequences

K
          
            k
          
        
        (
        s
        )
        =
        {
        s
        (
        
          k
          
            e
          
        
        n
        +
        r
        
          )
          
            n
            ≥
            0
          
        
        :
        e
        ≥
        0
        
           and 
        
        0
        ≤
        r
        ≤
        
          k
          
            e
          
        
        −
        1
        }
        .
      
    
    {\displaystyle K_{k}(s)=\{s(k^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.}

The sequence 
 
 
 
 s
 (
 n
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle s(n)_{n\geq 0}}
 
 is (R′, k)-regular (often shortened to just "k-regular") if the 
 
 
 
 
 R
 ′
 
 
 
 {\displaystyle R'}
 
-module generated by Kk(s) is a <a href="/facts/Finitely_generated_module/6Njcpgzr">finitely-generated</a> R′-<a href="/facts/Module_(mathematics)/jP0LIhFL">module</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
In the special case when 
 
 
 
 
 R
 ′
 
 =
 R
 =
 
 Q
 
 
 
 {\displaystyle R'=R=\mathbb {Q} }
 
, the sequence 
 
 
 
 s
 (
 n
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle s(n)_{n\geq 0}}
 
 is 
 
 
 
 k
 
 
 {\displaystyle k}
 
-regular if 
 
 
 
 
 K
 
 k
 
 
 (
 s
 )
 
 
 {\displaystyle K_{k}(s)}
 
 is contained in a finite-dimensional vector space over 
 
 
 
 
 Q
 
 
 
 {\displaystyle \mathbb {Q} }
 
.

<h3>Linear combinations</h3>
A sequence s(n) is k-regular if there exists an integer E such that, for all ej > E and 0 ≤ rj ≤ kej − 1, every subsequence of s of the form s(kejn + rj) is expressible as an R′-<a href="/facts/Linear_combination/CVjL6kuN">linear combination</a> 
 
 
 
 
 ∑
 
 i
 
 
 
 c
 
 i
 j
 
 
 s
 (
 
 k
 
 
 f
 
 i
 j
 
 
 
 
 n
 +
 
 b
 
 i
 j
 
 
 )
 
 
 {\displaystyle \sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})}
 
, where cij is an integer, fij ≤ E, and 0 ≤ bij ≤ kfij − 1.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
Alternatively, a sequence s(n) is k-regular if there exist an integer r and subsequences s1(n), ..., sr(n) such that, for all 1 ≤ i ≤ r and 0 ≤ a ≤ k − 1, every sequence si(kn + a) in the k-kernel Kk(s) is an R′-linear combination of the subsequences si(n).<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h3>Formal series</h3>
Let x0, ..., xk − 1 be a set of k non-commuting variables and let τ be a map sending some natural number n to the string xa0 ... xae − 1, where the base-k representation of x is the string ae − 1...a0. Then a sequence s(n) is k-regular if and only if the <a href="/facts/Formal_power_series/CNmaG0Vk">formal series</a> 
 
 
 
 
 ∑
 
 n
 ≥
 0
 
 
 s
 (
 n
 )
 τ
 (
 n
 )
 
 
 {\displaystyle \sum _{n\geq 0}s(n)\tau (n)}
 
 is 
 
 
 
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} }
 
-<a href="/facts/Rational_series/IRIx72YP">rational</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h3>Automata-theoretic</h3>
The formal series definition of a k-regular sequence leads to an automaton characterization similar to <a href="/facts/Marcel-Paul_Sch%25C3%25BCtzenberger/aF62Lo9H">Schützenberger</a>'s matrix machine.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="history">History</h2>
The notion of k-regular sequences was first investigated in a pair of papers by Allouche and Shallit.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> Prior to this, Berstel and Reutenauer studied the theory of <a href="/facts/Rational_series/IRIx72YP">rational series</a>, which is closely related to k-regular sequences.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="examples">Examples</h2>
<h3>Ruler sequence</h3>
Let 
 
 
 
 s
 (
 n
 )
 =
 
 ν
 
 2
 
 
 (
 n
 +
 1
 )
 
 
 {\displaystyle s(n)=\nu _{2}(n+1)}
 
 be the <a href="/facts/P-adic_valuation/wktvC3UP"> 
 
 
 
 2
 
 
 {\displaystyle 2}
 
-adic valuation</a> of 
 
 
 
 n
 +
 1
 
 
 {\displaystyle n+1}
 
. The ruler sequence 
 
 
 
 s
 (
 n
 
 )
 
 n
 ≥
 0
 
 
 =
 0
 ,
 1
 ,
 0
 ,
 2
 ,
 0
 ,
 1
 ,
 0
 ,
 3
 ,
 …
 
 
 {\displaystyle s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots }
 
 (<a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A007814) is 
 
 
 
 2
 
 
 {\displaystyle 2}
 
-regular, and the 
 
 
 
 2
 
 
 {\displaystyle 2}
 
-kernel

{
        s
        (
        
          2
          
            e
          
        
        n
        +
        r
        
          )
          
            n
            ≥
            0
          
        
        :
        e
        ≥
        0
        
           and 
        
        0
        ≤
        r
        ≤
        
          2
          
            e
          
        
        −
        1
        }
      
    
    {\displaystyle \{s(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}

is contained in the two-dimensional vector space generated by 
 
 
 
 s
 (
 n
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle s(n)_{n\geq 0}}
 
 and the constant sequence 
 
 
 
 1
 ,
 1
 ,
 1
 ,
 …
 
 
 {\displaystyle 1,1,1,\dots }
 
. These basis elements lead to the recurrence relations

s
                (
                2
                n
                )
              
              
                
                =
                0
                ,
              
            
            
              
                s
                (
                4
                n
                +
                1
                )
              
              
                
                =
                s
                (
                2
                n
                +
                1
                )
                −
                s
                (
                n
                )
                ,
              
            
            
              
                s
                (
                4
                n
                +
                3
                )
              
              
                
                =
                2
                s
                (
                2
                n
                +
                1
                )
                −
                s
                (
                n
                )
                ,
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}s(2n)&=0,\\s(4n+1)&=s(2n+1)-s(n),\\s(4n+3)&=2s(2n+1)-s(n),\end{aligned}}}

which, along with the initial conditions 
 
 
 
 s
 (
 0
 )
 =
 0
 
 
 {\displaystyle s(0)=0}
 
 and 
 
 
 
 s
 (
 1
 )
 =
 1
 
 
 {\displaystyle s(1)=1}
 
, uniquely determine the sequence.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h3>Thue–Morse sequence</h3>
The <a href="/facts/Thue%25E2%2580%2593Morse_sequence/1bvLMTBD">Thue–Morse sequence</a> t(n) (<a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A010060) is the <a href="/facts/Fixed_point_(mathematics)/vVVddTKc">fixed point</a> of the morphism 0 → 01, 1 → 10. It is known that the Thue–Morse sequence is 2-automatic. Thus, it is also 2-regular, and its 2-kernel

{
        t
        (
        
          2
          
            e
          
        
        n
        +
        r
        
          )
          
            n
            ≥
            0
          
        
        :
        e
        ≥
        0
        
           and 
        
        0
        ≤
        r
        ≤
        
          2
          
            e
          
        
        −
        1
        }
      
    
    {\displaystyle \{t(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}

consists of the subsequences 
 
 
 
 t
 (
 n
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle t(n)_{n\geq 0}}
 
 and 
 
 
 
 t
 (
 2
 n
 +
 1
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle t(2n+1)_{n\geq 0}}
 
.

<h3>Cantor numbers</h3>
The sequence of <a href="/facts/Cantor_set/6NUcMJvN">Cantor numbers</a> c(n) (<a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>: A005823) consists of numbers whose <a href="/facts/Ternary_numeral_system/bMUfR74P">ternary</a> expansions contain no 1s. It is straightforward to show that

c
                (
                2
                n
                )
              
              
                
                =
                3
                c
                (
                n
                )
                ,
              
            
            
              
                c
                (
                2
                n
                +
                1
                )
              
              
                
                =
                3
                c
                (
                n
                )
                +
                2
                ,
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}c(2n)&=3c(n),\\c(2n+1)&=3c(n)+2,\end{aligned}}}

and therefore the sequence of Cantor numbers is 2-regular. Similarly the <a href="/facts/Stanley_sequence/DhIA34rt">Stanley sequence</a>

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (sequence A005836 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>)
of numbers whose ternary expansions contain no 2s is also 2-regular.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h3>Sorting numbers</h3>
A somewhat interesting application of the notion of k-regularity to the broader study of algorithms is found in the analysis of the <a href="/facts/Merge_sort/A5jLYfzS">merge sort</a> algorithm. Given a list of n values, the number of comparisons made by the merge sort algorithm are the <a href="/facts/Sorting_number/DB9cVztD">sorting numbers</a>, governed by the recurrence relation

T
                (
                1
                )
              
              
                
                =
                0
                ,
              
            
            
              
                T
                (
                n
                )
              
              
                
                =
                T
                (
                ⌊
                n
                
                  /
                
                2
                ⌋
                )
                +
                T
                (
                ⌈
                n
                
                  /
                
                2
                ⌉
                )
                +
                n
                −
                1
                ,
                 
                n
                ≥
                2.
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}T(1)&=0,\\T(n)&=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n-1,\ n\geq 2.\end{aligned}}}

As a result, the sequence defined by the recurrence relation for merge sort, T(n), constitutes a 2-regular sequence.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

<h3>Other sequences</h3>
If 
 
 
 
 f
 (
 x
 )
 
 
 {\displaystyle f(x)}
 
 is an <a href="/facts/Integer-valued_polynomial/WNxvTVjE">integer-valued polynomial</a>, then 
 
 
 
 f
 (
 n
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle f(n)_{n\geq 0}}
 
 is k-regular for every 
 
 
 
 k
 ≥
 2
 
 
 {\displaystyle k\geq 2}
 
.
The <a href="/facts/Gould%2527s_sequence/E9l1VWg0">Glaisher–Gould</a> sequence is 2-regular. The Stern–Brocot sequence is 2-regular.
Allouche and Shallit give a number of additional examples of k-regular sequences in their papers.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="properties">Properties</h2>
k-regular sequences exhibit a number of interesting properties.

<ul><li>Every <a href="/facts/Automatic_sequence/Y829JY1k">k-automatic sequence</a> is k-regular.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a></li>
<li>Every <a href="/facts/K-synchronized_sequence/e2GJGBgN">k-synchronized sequence</a> is k-regular.</li>
<li>A k-regular sequence takes on finitely many values if and only if it is k-automatic.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> This is an immediate consequence of the class of k-regular sequences being a generalization of the class of k-automatic sequences.</li>
<li>The class of k-regular sequences is closed under termwise addition, termwise multiplication, and <a href="/facts/Convolution/PVPrdz9J">convolution</a>. The class of k-regular sequences is also closed under scaling each term of the sequence by an integer λ.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a><a class="footnote-ref" id="fnref:16" href="#fn:16">16</a><a class="footnote-ref" id="fnref:17" href="#fn:17">17</a><a class="footnote-ref" id="fnref:18" href="#fn:18">18</a> In particular, the set of k-regular <a href="/facts/Power_series/vYh6sTps">power series</a> forms a ring.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a></li>
<li>If 
 
 
 
 s
 (
 n
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle s(n)_{n\geq 0}}
 
 is k-regular, then for all integers 
 
 
 
 m
 ≥
 1
 
 
 {\displaystyle m\geq 1}
 
, 
 
 
 
 (
 s
 (
 n
 )
 
 mod
 
 m
 
 
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle (s(n){\bmod {m}})_{n\geq 0}}
 
 is k-automatic. However, the converse does not hold.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a></li>
<li>For multiplicatively independent k, l ≥ 2, if a sequence is both k-regular and l-regular, then the sequence satisfies a linear recurrence.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a> This is a generalization of a result due to Cobham regarding sequences that are both k-automatic and l-automatic.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a></li>
<li>The nth term of a k-regular sequence of integers grows at most polynomially in n.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a></li>
<li>If 
 
 
 
 F
 
 
 {\displaystyle F}
 
 is a field and 
 
 
 
 x
 ∈
 F
 
 
 {\displaystyle x\in F}
 
, then the sequence of powers 
 
 
 
 (
 
 x
 
 n
 
 
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle (x^{n})_{n\geq 0}}
 
 is k-regular if and only if 
 
 
 
 x
 =
 0
 
 
 {\displaystyle x=0}
 
 or 
 
 
 
 x
 
 
 {\displaystyle x}
 
 is a <a href="/facts/Root_of_unity/EqH0ho1Y">root of unity</a>.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a></li></ul>
<h2 id="proving-and-disproving-k-regularity">Proving and disproving k-regularity</h2>
Given a candidate sequence 
 
 
 
 s
 =
 s
 (
 n
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle s=s(n)_{n\geq 0}}
 
 that is not known to be k-regular, k-regularity can typically be proved directly from the definition by calculating elements of the kernel of 
 
 
 
 s
 
 
 {\displaystyle s}
 
 and proving that all elements of the form 
 
 
 
 (
 s
 (
 
 k
 
 r
 
 
 n
 +
 e
 )
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle (s(k^{r}n+e))_{n\geq 0}}
 
 with 
 
 
 
 r
 
 
 {\displaystyle r}
 
 sufficiently large and 
 
 
 
 0
 ≤
 e
 <
 
 2
 
 r
 
 
 
 
 {\displaystyle 0\leq e<2^{r}}
 
 can be written as linear combinations of kernel elements with smaller exponents in the place of 
 
 
 
 r
 
 
 {\displaystyle r}
 
. This is usually computationally straightforward.
On the other hand, disproving k-regularity of the candidate sequence 
 
 
 
 s
 
 
 {\displaystyle s}
 
 usually requires one to produce a 
 
 
 
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} }
 
-linearly independent subset in the kernel of 
 
 
 
 s
 
 
 {\displaystyle s}
 
, which is typically trickier. Here is one example of such a proof.
Let 
 
 
 
 
 e
 
 0
 
 
 (
 n
 )
 
 
 {\displaystyle e_{0}(n)}
 
 denote the number of 
 
 
 
 0
 
 
 {\displaystyle 0}
 
's in the binary expansion of 
 
 
 
 n
 
 
 {\displaystyle n}
 
. Let 
 
 
 
 
 e
 
 1
 
 
 (
 n
 )
 
 
 {\displaystyle e_{1}(n)}
 
 denote the number of 
 
 
 
 1
 
 
 {\displaystyle 1}
 
's in the binary expansion of 
 
 
 
 n
 
 
 {\displaystyle n}
 
. The sequence 
 
 
 
 f
 (
 n
 )
 :=
 
 e
 
 0
 
 
 (
 n
 )
 −
 
 e
 
 1
 
 
 (
 n
 )
 
 
 {\displaystyle f(n):=e_{0}(n)-e_{1}(n)}
 
 can be shown to be 2-regular. The sequence 
 
 
 
 g
 =
 g
 (
 n
 )
 :=
 
 |
 
 f
 (
 n
 )
 
 |
 
 
 
 {\displaystyle g=g(n):=|f(n)|}
 
 is, however, not 2-regular, by the following argument. Suppose 
 
 
 
 (
 g
 (
 n
 )
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle (g(n))_{n\geq 0}}
 
 is 2-regular. We claim that the elements 
 
 
 
 g
 (
 
 2
 
 k
 
 
 n
 )
 
 
 {\displaystyle g(2^{k}n)}
 
 for 
 
 
 
 n
 ≥
 1
 
 
 {\displaystyle n\geq 1}
 
 and 
 
 
 
 k
 ≥
 0
 
 
 {\displaystyle k\geq 0}
 
 of the 2-kernel of 
 
 
 
 g
 
 
 {\displaystyle g}
 
 are linearly independent over 
 
 
 
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} }
 
. The function 
 
 
 
 n
 ↦
 
 e
 
 0
 
 
 (
 n
 )
 −
 
 e
 
 1
 
 
 (
 n
 )
 
 
 {\displaystyle n\mapsto e_{0}(n)-e_{1}(n)}
 
 is surjective onto the integers, so let 
 
 
 
 
 x
 
 m
 
 
 
 
 {\displaystyle x_{m}}
 
 be the least integer such that 
 
 
 
 
 e
 
 0
 
 
 (
 
 x
 
 m
 
 
 )
 −
 
 e
 
 1
 
 
 (
 
 x
 
 m
 
 
 )
 =
 m
 
 
 {\displaystyle e_{0}(x_{m})-e_{1}(x_{m})=m}
 
. By 2-regularity of 
 
 
 
 (
 g
 (
 n
 )
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle (g(n))_{n\geq 0}}
 
, there exist 
 
 
 
 b
 ≥
 0
 
 
 {\displaystyle b\geq 0}
 
 and constants 
 
 
 
 
 c
 
 i
 
 
 
 
 {\displaystyle c_{i}}
 
 such that for each 
 
 
 
 n
 ≥
 0
 
 
 {\displaystyle n\geq 0}
 
,

∑
          
            0
            ≤
            i
            ≤
            b
          
        
        
          c
          
            i
          
        
        g
        (
        
          2
          
            i
          
        
        n
        )
        =
        0.
      
    
    {\displaystyle \sum _{0\leq i\leq b}c_{i}g(2^{i}n)=0.}

Let 
 
 
 
 a
 
 
 {\displaystyle a}
 
 be the least value for which 
 
 
 
 
 c
 
 a
 
 
 ≠
 0
 
 
 {\displaystyle c_{a}\neq 0}
 
. Then for every 
 
 
 
 n
 ≥
 0
 
 
 {\displaystyle n\geq 0}
 
,

g
        (
        
          2
          
            a
          
        
        n
        )
        =
        
          ∑
          
            a
            +
            1
            ≤
            i
            ≤
            b
          
        
        −
        (
        
          c
          
            i
          
        
        
          /
        
        
          c
          
            a
          
        
        )
        g
        (
        
          2
          
            i
          
        
        n
        )
        .
      
    
    {\displaystyle g(2^{a}n)=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})g(2^{i}n).}

Evaluating this expression at 
 
 
 
 n
 =
 
 x
 
 m
 
 
 
 
 {\displaystyle n=x_{m}}
 
, where 
 
 
 
 m
 =
 0
 ,
 −
 1
 ,
 1
 ,
 2
 ,
 −
 2
 
 
 {\displaystyle m=0,-1,1,2,-2}
 
 and so on in succession, we obtain, on the left-hand side

g
        (
        
          2
          
            a
          
        
        
          x
          
            m
          
        
        )
        =
        
          |
        
        
          e
          
            0
          
        
        (
        
          x
          
            m
          
        
        )
        −
        
          e
          
            1
          
        
        (
        
          x
          
            m
          
        
        )
        +
        a
        
          |
        
        =
        
          |
        
        m
        +
        a
        
          |
        
        ,
      
    
    {\displaystyle g(2^{a}x_{m})=|e_{0}(x_{m})-e_{1}(x_{m})+a|=|m+a|,}

and on the right-hand side,

∑
          
            a
            +
            1
            ≤
            i
            ≤
            b
          
        
        −
        (
        
          c
          
            i
          
        
        
          /
        
        
          c
          
            a
          
        
        )
        
          |
        
        m
        +
        i
        
          |
        
        .
      
    
    {\displaystyle \sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}

It follows that for every integer 
 
 
 
 m
 
 
 {\displaystyle m}
 
,

|
        
        m
        +
        a
        
          |
        
        =
        
          ∑
          
            a
            +
            1
            ≤
            i
            ≤
            b
          
        
        −
        (
        
          c
          
            i
          
        
        
          /
        
        
          c
          
            a
          
        
        )
        
          |
        
        m
        +
        i
        
          |
        
        .
      
    
    {\displaystyle |m+a|=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}

But for 
 
 
 
 m
 ≥
 −
 a
 −
 1
 
 
 {\displaystyle m\geq -a-1}
 
, the right-hand side of the equation is monotone because it is of the form 
 
 
 
 A
 m
 +
 B
 
 
 {\displaystyle Am+B}
 
 for some constants 
 
 
 
 A
 ,
 B
 
 
 {\displaystyle A,B}
 
, whereas the left-hand side is not, as can be checked by successively plugging in 
 
 
 
 m
 =
 −
 a
 −
 1
 
 
 {\displaystyle m=-a-1}
 
, 
 
 
 
 m
 =
 −
 a
 
 
 {\displaystyle m=-a}
 
, and 
 
 
 
 m
 =
 −
 a
 +
 1
 
 
 {\displaystyle m=-a+1}
 
. Therefore, 
 
 
 
 (
 g
 (
 n
 )
 
 )
 
 n
 ≥
 0
 
 
 
 
 {\displaystyle (g(n))_{n\geq 0}}
 
 is not 2-regular.<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a>

<h2 id="notes">Notes</h2>

<ul><li>Allouche, Jean-Paul; <a href="/facts/Jeffrey_Shallit/4bmJgyIH">Shallit, Jeffrey</a> (1992), "The ring of k-regular sequences", Theoret. Comput. Sci., 98 (2): 163–197, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0304-3975%2892%2990001-v">10.1016/0304-3975(92)90001-v</a>.</li>
<li>Allouche, Jean-Paul; <a href="/facts/Jeffrey_Shallit/4bmJgyIH">Shallit, Jeffrey</a> (2003), "The ring of k-regular sequences, II", Theoret. Comput. Sci., 307: 3–29, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fs0304-3975%2803%2900090-2">10.1016/s0304-3975(03)00090-2</a>.</li>
<li>Allouche, Jean-Paul; <a href="/facts/Jeffrey_Shallit/4bmJgyIH">Shallit, Jeffrey</a> (2003). Automatic Sequences: Theory, Applications, Generalizations. <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-82332-6. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1086.11015">1086.11015</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Allouche and Shallit (1992), Definition 2.1. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Allouche & Shallit (1992), Theorem 2.2. <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Allouche & Shallit (1992), Theorem 2.2. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Allouche & Shallit (1992), Theorem 4.3. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Allouche & Shallit (1992), Theorem 4.4. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Schützenberger, M.-P. (1961), "On the definition of a family of automata", Information and Control, 4 (2–3): 245–270, doi:10.1016/S0019-9958(61)80020-X. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Allouche & Shallit (1992, 2003). <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Berstel, Jean; Reutenauer, Christophe (1988). Rational Series and Their Languages. EATCS Monographs on Theoretical Computer Science. Vol. 12. Springer-Verlag. ISBN 978-3-642-73237-9. <a href="978-3-642-73237-9" target="_blank">978-3-642-73237-9</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Allouche & Shallit (1992), Example 8. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Allouche & Shallit (1992), Examples 3 and 26. <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Allouche & Shallit (1992), Example 28. <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Allouche & Shallit (1992, 2003). <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Allouche & Shallit (1992), Theorem 2.3. <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Allouche & Shallit (2003) p. 441. <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Allouche & Shallit (2003) p. 441. <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Allouche & Shallit (1992), Theorem 2.5. <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Allouche & Shallit (1992), Theorem 3.1. <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Allouche & Shallit (2003) p. 445. <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Allouche and Shallit (2003) p. 446. <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Allouche and Shallit (2003) p. 441. <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Bell, J. (2006). "A generalization of Cobham's theorem for regular sequences". Séminaire Lotharingien de Combinatoire. 54A. <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Cobham, A. (1969). "On the base-dependence of sets of numbers recognizable by finite automata". Math. Systems Theory. 3 (2): 186–192. doi:10.1007/BF01746527. S2CID 19792434. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Allouche & Shallit (1992) Theorem 2.10. <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Allouche and Shallit (2003) p. 444. <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Allouche and Shallit (1993) p. 168–169. <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
</ol>

k-regular sequence open-in-new

k-regular sequence