Binary sequences meet the Fibonacci sequence
2024
Read Binary sequences meet the Fibonacci sequence (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11319.txt.
Introduction
Piotr Miska, Bartosz Sobolewski, and Maciej Ulas study a new family of number sequences built in the style of the Fibonacci sequence. Each new term blends two earlier terms, but how far back it reaches is steered by a binary sequence of zeros and ones. The team focuses on the ratios between neighboring terms and the set of values those ratios take.
For some steering sequences, including the famous Prouhet-Thue-Morse sequence, the ratio set stays finite and follows an automatic pattern. The authors prove this with help from a software prover. For other steering sequences, the ratio set runs infinite. When the steering sequence settles into a repeating tail, they sort the ratio sets into three types by shape. The work links two classic corners of number theory.
Catalog record
| YEAR | 2024 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-11319
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Binary sequences meet the Fibonacci sequence Thanks: * Corresponding author E-mail: [email protected] , miskap.ujs.sk (P. Miska), [email protected] (B. Sobolewski), [email protected] (M. Ulas) Abstract . We introduce a new family of meta-Fibonacci sequences ( f ( n ) ) n ∈ ℕ (f(n))_{n\in\mathbb{N}} , governed by the recurrence relation f ( n ) = a f ( n − u n − 1 ) + b f ( n − u n − 2 ) , f(n)=af(n-u_{n}-1)+bf(n-u_{n}-2), where 𝐮 = ( u n ) n ∈ ℕ \mathbf{u}=(u_{n})_{n\in\mathbb{N}} is a sequence with values 0 , 1 0,1 . Our study focuses on the properties of the sequence of quotients h ( n ) = f ( n + 1 ) / f ( n ) h(n)=f(n+1)/f(n) and its set of values 𝒱 ( f ) = { h ( n ) : n ∈ ℕ } \mathcal{V}(f)=\{h(n):n\in\mathbb{N}\} for various 𝐮 \mathbf{u} . We give a sufficient condition for finiteness of 𝒱 ( f ) \mathcal{V}(f) and automaticity of ( h ( n ) ) n ∈ ℕ (h(n))_{n\in\mathbb{N}} , which holds in particular when 𝐮 \mathbf{u} is the famous Prouhet-Thue-Morse sequence. In the automatic case, a constructive approach is used, with the help of the software Walnut . On the other hand, we prove that the set 𝒱 ( { ) \cal{V}(f) is infinite for other special binary sequences 𝐮 \mathbf{u} , and obtain a trichotomy in its topological type when 𝐮 \mathbf{u} is eventually periodic. 2020 Mathematics Subject Classification 11B37, 11B39, 11B83, 11B85 Piotr Miska a, b , Bartosz Sobolewski a, * , Maciej Ulas a a Jagiellonian University, Faculty of Mathematics and Computer Science, Institute of Mathematics, Łojasiewicza 6, 30-348 Kraków, Poland b J. Selye University, Faculty of Economics and Informatics, Department of Mathematics Hradná 167/21, P. O. Box 54, 945 01 Komárno, Slovakia 1. Introduction and motivation Let a,b\in\mathbb{Z} and recall that by a binary linear recurrence sequence we mean a sequence (g(n))_{n\in\mathbb{N}} satisfying the recurrence relation (1) g(n)=ag(n-1)+bg(n-2), where g(0),g(1) are given. The most extensively studied example is of course the Fibonacci sequence, which arises for a=b=1 and g(0)=0,g(1)=1 . In the literature there are many variations of binary recurrence sequences, including so- called meta-Fibonacci sequences. What is a meta-Fibonacci sequence? In the most general terms, it is a solution of a recurrence relation of the form (2) f(n)=f(r_{1}(n))+f(r_{2}(n)), where r_{1}(n),r_{2}(n) are certain expressions involving n,f(n-1),\ldots,f(n-k) and possibly other functions of n . We note that the class of sequences defined in this way is much broader than the one introduced by Conolly in [ 8 ] . Special meta-Fibonacci sequences were investigated in [ 11 , 12 , 16 ] . Probably the most famous one is Hofstadter’s Q -sequence (see [ 12 , page 137] ), defined by Q(1)=Q(2)=1 and Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2)) for n\geq 2 . It is an open question whether the sequence is infinite, i.e., whether for each n\in\mathbb{N} one can compute the value of Q(n) . In the paper, we consider a new variation of binary recurrence sequences, where the indices on the right-hand side of ( 1 ) are additionally shifted, depending on a given sequence \mathbf{u}=(u_{n})_{n\in\mathbb{N}} with values in the set \{0,1\} . More precisely, we are interested in (f(n))_{n\in\mathbb{N}} satisfying (3) f(n)=af(n-u_{n}-1)+bf(n-u_{n}-2), where a,b\in\mathbb{Z} . In other words, the values u_{n} are responsible for switching between a binary and ternary recurrence relation. For the most part, we consider the initial conditions f(0)=1,\quad f(1)=1,\quad f(2)=a+b. This will turn out to be a natural choice in the context of our results — see Section 2 for a short discussion. The present study arose from the observation that in the case \mathbf{u}=(T_{n})_{n\in\mathbb{N}} , the famous Prouhet–Thue–Morse sequence (PTM sequence for short), subsequent terms f(n) have surprisingly many common prime factors, regardless of the parameters a,b . Contrast this with usual binary recurrence sequences ( 1 ), where for a,b,g(0),g(1) pairwise coprime one can show inductively that g(n),g(n+1) are coprime for all n\in\mathbb{N} . This leads us to studying the set of ratios \cal{V}(f):=\{f(n+1)/f(n):n\in\mathbb{N}\}, which turns out to be finite in the case \mathbf{u}=(T_{n})_{n\in\mathbb{N}} , as we prove in Theorem 3.1 below. We note that for a binary linear recurrence sequence (g(n))_{n\in\mathbb{N}} the sequence of ratios of consecutive terms is known to be either convergent, periodic, or dense in some circle or line in the complex plane (see [ 5 , 7 ] ). It is thus interesting to see what may change in the structure of the set (or sequence) of ratios if we modify the recurrence relation as described. Apart from the PTM sequence, we study the more general case when \mathbf{u} belongs to the class of automatic sequences , which supplies many natural examples of 0 - 1 sequences. We recall the definition of automatic sequences and their essential properties in Section 3 . A different kind of connection between meta-Fibonacci sequences (more specifically, a relative of Hofstadter’s Q -sequence) and automatic sequences is investigated in [ 4 ] . Finiteness of \cal{V}(f) turns out to be a direct consequence of the key property that consecutive terms 0,1,0 occur in the PTM sequence with bounded gaps. We thus also investigate the case when the sequence \mathbf{u} does not satisfy said property but potentially has some other structure. To conclude this section, we describe the content of the paper in some more detail. In Section 3 we investigate the solutions of ( 3 ) in the case when \mathbf{u}=(T_{n})_{n\in\mathbb{N}} is the PTM sequence. We prove that the set \cal{V}(f) of quotients of consecutive terms of (f(n))_{n\in\mathbb{N}} contains exactly 7 elements (Theorem 3.1 ). Motivated by this, in Section 4 we obtain a similar result for a broader class of sequences, where the recurrence ( 2 ) is governed by two binary sequences. Section 5 describes another, more constructive approach to proving these results using the software Walnut [ 13 ] . In Section 6 we investigate the case when u contains arbitrarily long blocks of zeros, and prove that, under certain conditions, the set \cal{V}(f) contains the set of ratios \cal{V}(g) of a binary recurrence sequence (g(n))_{n\in\mathbb{N}} . We also consider ultimately periodic u , in which case the set \cal{V}(f) turns out to be finite, have finitely many accumulation points, or be dense in \mathbb{R} . Finally, in Section 7 we present further remarks concerning possible generalization and offer some general conjectures. 2. Notation and basic observations Throughout the remainder of the paper we assume that \mathbf{u} is a given binary sequence and let (f(n))_{n\in\mathbb{N}} denote the sequence defined by the recurrence ( 3 ) and initial conditions f(0)=f(1)=1,f(2)=a+b . We consider the sequence of ratios h(n):=\frac{f(n+1)}{f(n)}, which will be our main object of study along with the set \cal{V}(f)=\{h(n):n\in\mathbb{N}\} . We may view f(n) and h(n) in two ways: (i) as number sequences for fixed a,b\in\mathbb{Z} ; (ii) as sequences of rational functions in variables a,b . Usually, both cases can be treated in the same way so by default when writing f(n),h(n) we mean the first interpretation. The rational function approach is convenient when we need to eliminate the possibility f(n)=0 , in which case h(n)