A study of a family of self-referential sequences: asymptotics, exact forms and combinatorial connections
Benoit Cloitre · 2025
Read A study of a family of self-referential sequences: asymptotics, exact forms and combinatorial connections by Benoit Cloitre (2025) 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-2506-18103.txt.
Introduction
Benoit Cloitre studies integer sequences that consult their own past, in this 2025 paper. Each sequence starts from a chosen value, then steps by one amount when the current index has already shown up as a term, and by another amount when it has not. Simple as the rule sounds, it breeds a whole zoo of behaviors, many logged piecemeal in sequence databases.
Cloitre analyzes the main families in depth. For one broad range of settings, the growth rate settles at a value given by a quadratic formula. Two families yield exact formulas, others turn periodic, and some trace lattice patterns. Tree pictures tie the family to Fibonacci-style recursions.
Catalog record
| CREATOR | Benoit Cloitre |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-18103
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A study of a family of self-referential sequences: asymptotics, exact forms and combinatorial connections Benoit Cloitre Abstract We introduce and analyze a three-parameter family of self-referential integer sequences S ( x , y , z ) S(x,y,z) : starting from a ( 1 ) = x a(1)=x , each term advances by y y when the index k k has already appeared as a value and by z z otherwise. This simple rule generates a surprising zoo of behaviors, many of which are catalogued—albeit in a rather unstructured fashion—in the OEIS. Whenever y > z > 0 y>z>0 , we prove that the density a ( k ) / k a(k)/k converges to the positive root of r 2 − z r − ( y − z ) = 0 r^{2}-zr-(y-z)=0 . Two subfamilies, S ( x , Z + 1 , Z ) S(x,Z+1,Z) and S ( x , Z , Z + 1 ) S(x,Z,Z+1) , yield explicit non-homogeneous Beatty sequences, providing explicit formulas for numerous OEIS entries. For y = 0 y=0 and z ≥ 2 z\geq 2 , the sequences eventually become periodic and satisfy linear recurrences. Critical cases with a zero discriminant unveil geometric patterns on triangular, square, and hexagonal lattices. Finally, via tree-like representations we uncover a tight link with meta-Fibonacci recurrences and highlight unexpected phenomena when y < 0 y<0 . These results position S ( x , y , z ) S(x,y,z) as a unifying framework connecting additive combinatorics, number theory, and discrete dynamics. 1 Introduction and definitions Self-referential integer sequences, where the rule for generating the next term depends on the sequence’s history, often yield intricate global structures from simple local rules. Their appeal lies in understanding the emergence of complex, predictable behavior from recursive definitions. Such sequences frequently appear in combinatorial number theory and have connections to fractal geometry, dynamical systems, and combinatorics. In our 2003 paper, "Numerical analogues of Aronson’s sequence" [ 3 ] , we announced our intention to study the following family of sequences. Definition 1.1: The S(x,y,z) family Let x,y,z\in\mathbb{N} . The sequence (a(k))_{k\geq 1} is defined by: (i) a(1)=x . (ii) For k>1 , let \mathcal{A}_{k-1}=\{a(1),\dots,a(k-1)\} . Then, a(k)=\begin{cases}a(k-1)+y&\text{if }k\in\mathcal{A}_{k-1}\quad(\text{a \emph{hit}}),\\ a(k-1)+z&\text{if }k\notin\mathcal{A}_{k-1}\quad(\text{a \emph{miss}}).\end{cases} At the time, a lack of a cohesive framework and general results compelled us to postpone a detailed study. Over twenty years later, this paper fulfills that original goal. We believe this work demonstrates the rich structure of these sequences, offering significant points of interest for number theorists and combinatorists alike, particularly in the areas of combinatorics on words and enumerative problems. The structure of this paper is as follows. In Section 2 , we establish the general asymptotic linearity of the sequences for the case y>z>0 . Section 3 is dedicated to two important subfamilies that generate non-homogeneous Beatty sequences, providing explicit formulas for many OEIS entries. In Section 4 , we analyze the case where y=0 , which leads to ultimately periodic sequences satisfying linear recurrences. Section 5 explores cases where the characteristic discriminant vanishes, revealing deep connections to combinatorial objects like triangular, square, and hexagonal numbers. Finally, in Section 6 , we establish a formal bridge between our sequences and the theory of meta-Fibonacci sequences, uncovering a shared combinatorial foundation. 2 Asymptotic linearity for y>z>0 We first establish that when the hit increment y exceeds the miss increment z , the sequence exhibits a stable asymptotic slope. Let r_{0} be the positive root of the characteristic equation r^{2}-zr-(y-z)=0 : r_{0}=\frac{z+\sqrt{z^{2}+4(y-z)}}{2}. This root satisfies the equilibrium equation r_{0}=z+\frac{y-z}{r_{0}} . Theorem 2.1: Main asymptotic result For a sequence S(x,y,z) with y>z>0 , \lim_{n\to\infty}\frac{a(n)}{n}=r_{0}. Proof Step 1: Exact relation. By definition: a(n)-a(n-1)=z+(y-z)\cdot\mathbf{1}_{\{n\in\mathcal{A}_{n-1}\}}. Summing for k=2 to n : a(n)-a(1)=z(n-1)+(y-z)H_{n}, where H_{n}=\sum_{k=2}^{n}\mathbf{1}_{\{k\in\mathcal{A}_{k-1}\}} is the number of hits up to step n . Thus: \boxed{a(n)=x+z(n-1)+(y-z)H_{n}.} Step 2: Link between H_{n} and the counting function. Let N(t)=\max\{k\mid a(k)\leq t\} be the counting function of the sequence. • Key property: k\in\mathcal{A}_{k-1} if and only if k is in the image of the sequence, i.e., \exists j<k such that a(j)=k . • Thus H_{n}=|\{k\in\{2,\dots,n\}\mid k\in\operatorname{im}(a)\}| . • Since N(n)=\max\{k\mid a(k)\leq n\} , we have: H_{n}=N(n)-\mathbf{1}_{\{1\in\operatorname{im}(a)\}}+O(1)=N(n)+O(1), since \mathbf{1}_{\{1\in\operatorname{im}(a)\}} is constant (0 or 1). We deduce: \frac{H_{n}}{n}=\frac{N(n)}{n}+O\left(\frac{1}{n}\right). Step 3: Asymptotic analysis via \limsup and \liminf . Let: \overline{r}=\limsup_{n\to\infty}\frac{a(n)}{n},\quad\underline{r}=\liminf_{n\to\infty}\frac{a(n)}{n}. From the equation in Step 1: \frac{a(n)}{n}=\frac{x}{n}+z\frac{n-1}{n}+(y-z)\frac{H_{n}}{n}. Taking upper and lower limits, and using \frac{H_{n}}{n}=\frac{N(n)}{n}+O(1/n) : \boxed{\overline{r}=z+(y-z)\limsup_{n\to\infty}\frac{N(n)}{n},\quad\underline{r}=z+(y-z)\liminf_{n\to\infty}\frac{N(n)}{n}.} Step 4: Duality between sequence and counting function. Lemma 2.2: Density-counting duality relation Let (a(n))_{n\in\mathbb{N}^{*}} be a strictly increasing sequence of real numbers such that \lim_{n\to\infty}a(n)=+\infty . Let N:\mathbb{R}\to\mathbb{N} be the counting function defined by N(t)=\max\{k\in\mathbb{N}\mid a(k)\leq t\} . Define the limit superior and limit inferior of the sequence’s rate of growth as: \overline{r}=\limsup_{n\to\infty}\frac{a(n)}{n}\quad\text{and}\quad\underline{r}=\liminf_{n\to\infty}\frac{a(n)}{n}. Then the following duality relations hold: \limsup_{t\to\infty}\frac{N(t)}{t}=\frac{1}{\underline{r}}\quad\text{and}\quad\liminf_{t\to\infty}\frac{N(t)}{t}=\frac{1}{\overline{r}}. Proof of Lemma 2 . The proof is based on the fundamental inequality derived from the definition of the counting function N(t) . Step 1: The fundamental inequality. By definition, a(N(t)) is the largest term in the sequence that is less than or equal to t . This directly implies: a(N(t))\leq t<a(N(t)+1). This inequality holds for all t\geq a(1) . Step 2: Bounding the ratio N(t)/t . We manipulate the fundamental inequality to establish a tight bound on the ratio N(t)/t . From the left side, a(N(t))\leq t , we invert to get \frac{1}{t}\leq\frac{1}{a(N(t))} , which implies: \frac{N(t)}{t}\leq\frac{N(t)}{a(N(t))}. From the right side, t<a(N(t)+1) , we similarly get \frac{1}{a(N(t)+1)}<\frac{1}{t} , which implies: \frac{N(t)}{a(N(t)+1)}<\frac{N(t)}{t}. Combining these gives the sandwich inequality: \frac{N(t)}{a(N(t)+1)}<\frac{N(t)}{t}\leq\frac{N(t)}{a(N(t))}.\quad(*) Step 3: Asymptotic analysis. We now analyze the limits of the bounding terms in (*) as t\to\infty . Let v_{k}=k/a(k) . We are comparing the asymptotic behavior of v_{N(t)} with that of the sequence (v_{k}) . The function N(t) is a non-decreasing step function from [a(1),\infty) onto \mathbb{N} . Because it is non-decreasing and surjective onto the integers, the set of accumulation points of the function v_{N(t)} as t\to\infty is identical to the set of accumulation points of the sequence (v_{k})_{k\to\infty} . Therefore, their respective limsup and liminf are equal. Let’s apply this to our bounds. For the right-hand side of (*) : \limsup_{t\to\infty}\frac{N(t)}{a(N(t))}=\limsup_{k\to\infty}\frac{k}{a(k)}=\frac{1}{\liminf_{k\to\infty}\frac{a(k)}{k}}=\frac{1}{\underline{r}}. For the left-hand side of (*) , we rewrite it as \frac{N(t)}{N(t)+1}\cdot\frac{N(t)+1}{a(N(t)+1)} . Since \lim_{t\to\infty}\frac{N(t)}{N(t)+1}=1 , we have: \limsup_{t\to\infty}\frac{N(t)}{a(N(t)+1)}=1\cdot\limsup_{t\to\infty}\frac{N(t)+1}{a(N(t)+1)}=\limsup_{k\to\infty}\frac{k}{a(k)}=\frac{1}{\underline{r}}. Step 4: Conclusion by the squeeze theorem. Taking the \limsup across the inequality (*) yields: \frac{1}{\underline{r}}\leq\limsup_{t\to\infty}\frac{N(t)}{t}\leq\frac{1}{\underline{r}}. This proves the first relation: \limsup_{t\to\infty}\frac{N(t)}{t}=\frac{1}{\underline{r}} . The argument for the second relation is identical. Taking the \liminf across (*) : \liminf_{t\to\infty}\frac{N(t)}{a(N(t)+1)}\leq\liminf_{t\to\infty}\frac{N(t)}{t}\leq\liminf_{t\to\infty}\frac{N(t)}{a(N(t))}. Both the left and right bounds evaluate to \frac{1}{\limsup_{k\to\infty}\frac{a(k)}{k}}=\frac{1}{\overline{r}} . Thus: \frac{1}{\overline{r}}\leq\liminf_{t\to\infty}\frac{N(t)}{t}\leq\frac{1}{\overline{r}}. This proves the second relation: \liminf_{t\to\infty}\frac{N(t)}{t}=\frac{1}{\overline{r}} . \blacksquare Step 5: System of equations and uniqueness of the limit. Injecting Lemma 2 into the equations from Step 3: \overline{r}=z+\frac{y-z}{\underline{r}},\quad\underline{r}=z+\frac{y-z}{\overline{r}}. Multiplying the first equation by \underline{r} , the second by \overline{r} : \overline{r}\underline{r}=z\underline{r}+(y-z),\quad\underline{r}\overline{r}=z\overline{r}+(y-z). By equality of the right-hand sides: z\underline{r}+(y-z)=z\overline{r}+(y-z)\implies z\underline{r}=z\overline{r}\implies\underline{r}=\overline{r}\quad(\text{since }z>0). The limit r=\lim_{n\to\infty}\frac{a(n)}{n} therefore exists. Step 6: Solving the characteristic equation. The equation r=z+\frac{y-z}{r} becomes r^{2}-zr-(y-z)=0 . Since r>0 (as a(n)\geq n\min(y,z)+O(1) ), we have: \boxed{r=\frac{z+\sqrt{z^{2}+4(y-z)}}{2}=r_{0}.} \blacksquare 3 Beatty sequences In this section, we show that sequences from the families S(x,Z+1,Z) (family A) and S(x,Z,Z+1) (family B) correspond to non-homogeneous Beatty sequences. To distinguish these specific integer values from the formal parameters of