Pointwise Order of Generalized Hofstadter Functions G, H, and Beyond

Pierre Letouzey

IRIF

Université Paris Cité, CNRS, Inria

F-75013 Paris

France

letouzey@irif.fr

Shuo Li

Hangzhou International Innovation Institute

Beihang University 166 Shuanghongqiao Street

Pingyao Town, Yuhang District, Hangzhou, 311115

China

shuoli@buaa.edu.cn

Wolfgang Steiner

IRIF

Université Paris Cité, CNRS

F-75013 Paris

France

steiner@irif.fr

Abstract

Hofstadter’s G function is recursively defined via G(0) = 0 and then G(n) = n − G(G(n − 1)). Following Hofstadter, we vary the number k of nested recursive calls in this equation and obtain a family of functions (F_{k}). Here we establish that this family is ordered pointwise: for all k and n, we have F_{k}(n) ≤ F_{k+1}(n). To achieve this, we make a detour via infinite morphic words generalizing the Fibonacci word. We prove various properties of these words, concerning the lengths of substituted prefixes of these words and the number of occurrences of specific letters in these prefixes. We also relate the limits of \frac{1}{n}F_{k}(n) to the frequencies of letters in the considered words. We provide a certified formalization of all these results in the Rocq proof assistant.

1 Introduction

1.1 The functions

For each integer k ≥ 1, we recursively define the function^{1}

F_{k} : ℕ → ℕ, n ↦ \begin{cases}0, & if n = 0; \\ n − F_{k}^{k}(n − 1), & otherwise. \end{cases}

The function F_{k} is well defined, since one may prove that 0 ≤ F_{k}(n) ≤ n for all n ≥ 0. This family of functions is due to Hofstadter [13, Chap. 5]. In particular, F_{2} is Hofstadter’s function G (see OEIS entry \underline{A005206} [22, 13, 5, 10]). Note that G(n) = ⌊(n + 1)/φ⌋ where φ is the golden ratio (1 + \sqrt{5})/2. Similarly, F_{3} is Hofstadter’s function H (see OEIS \underline{A005374}), and the generalization to higher degrees of recursive nesting in the definition of F_{k} was already suggested by Hofstadter [13]. To be complete, the OEIS database already includes F_{4} as \underline{A005375}, F_{5} as \underline{A005376}, and F_{6} as \underline{A100721}. On the other hand, we choose to start this sequence with F_{1}, where only one recursive call is done, leading to a function that can easily be shown to verify F_{1}(n) = ⌊(n + 1)/2⌋ = ⌈n/2⌉. Throughout this paper, we never consider the case k = 0: although the previous definition could be extended and gives a non-recursive function F_{0}, this F_{0} has too little in common with the other F_{k} functions to be of much interest.

1.2 A monotonicity problem

Small values of the functions F_{1} to F_{5} are displayed in Figure 1.1. From this figure, one may easily guess that F_{1} is everywhere below or equal to F_{2}, similarly that F_{2} is below or equal to F_{3}, and so forth. Indeed, our main result is the following theorem.

Theorem 1.1. For all k ≥ 1, n ≥ 0, we have F_{k}(n) ≤ F_{k+1}(n).

This property seems to defy any attempt to prove it directly via induction on the functions F_{k}. Therefore, a different approach is used. We relate each function F_{k} to a morphic word x_{k} and turn the function comparison into an equivalent statement about these words. This gives Theorem 7.4 below, which contains Theorem 1.1 as a special case.

1In all this work, the k-th exponent of a function denotes its k-th iterate. For instance, F_{2}^{2}(n) is F_{2}(F_{2}(n)), not the square of F_{2}(n).

0510 15 20 25 30 0510 15 20 25  \begin{matrix}id \\ F_{5} \\ F_{4} \\ F_{3} = H \\ F_{2} = G \\ F_{1} \end{matrix}

Figure 1.1: Plotting F_{1}, F_{2}, …, F_{5}

1.3 Substitutions and morphic words

For k ≥ 1, let τ_{k} be the substitution on the alphabet {1, 2, …, k} defined by

\begin{matrix}τ_{k} : k & ↦ k 1, \\ i & ↦ i + 1, for 1 ≤ i < k, \end{matrix}

and let x_{k} = x_{k}[0]x_{k}[1] ⋯ ∈ {1, 2, …, k}^{∞} be the fixed point of τ_{k}. Here, a substitution (or morphism) on an alphabet A is a map τ : A^{∗} → A^{∗} satisfying τ(uv) = τ(u)τ(v) for all u, v ∈ A^{∗}, where A^{∗} denotes the set of finite words with letters in A. The map τ is therefore defined by its value on the letters of A, and it is extended in a natural way to infinite words (or sequences) w = w[0]w[1] ⋯ ∈ A^{∞} by setting τ(x) = τ(x[0])τ(x[1]) · · ·. For more on substitutions, we refer to Pytheas Fogg [8].

These substitutions and words are not novel. For instance, τ_{1} operates on the singleton alphabet {1} in such a way that τ_{1}(1) = 11, and hence x_{1} = 1^{∞}. It is the only case where

x_{2} = 2122121221221212212122122121221221212212 ⋯
x_{3} = 3123313123123312331312331312312331312312 ⋯
x_{4} = 4123441412412341234412344141234414124123 ⋯
x_{5} = 5123455151251235123451234551234551512345 ⋯

Figure 1.2: Infinite words x_{2}, …, x_{5} (with largest letter in red)

x_{k} is ultimately periodic. For k = 2, we recover the well-known Fibonacci substitution and word.^{2} The substitution τ_{3} already appears (up to letter renaming) as σ(1, 0) in Pytheas Fogg [8, Ex. 8.1.2], as an example of a modified Jacobi–Perron substitution. More generally, the substitutions τ_{k} and words x_{k} can be associated with the Rényi expansion of 1 in base β_{k}, where β_{k} is the positive zero of X^{k} − X^{k−1} − 1, and were studied by Frougny, Masáková and Pelantová [9]. When k ≥ 2, this expansion can be written as 1(0)^{k−2}1. As a consequence, the factor complexity of x_{k} is n ↦ (k − 1)n + 1; in particular, x_{2} is Sturmian [9].

1.4 New results

In this article, in addition to the aforementioned monotonicity of F_{k} (Theorem 1.1), we exhibit several relations between the functions F_{k} and the words x_{k}. For instance, for k ≥ 1 and a position n ≥ 0, the value of x_{k}[n] is either the first index j ≤ k such that F_{k}^{j}(n + 1) = F_{k}^{j}(n), or k if there is no such small index; see Proposition 4.4 below. In particular, x_{k}[n] is the letter 1 exactly when F_{k}(n + 1) = F_{k}(n), and this also leads to the fact that F_{k}(n) is equal to the number of non-1 letters in the first n letters of x_{k}; see Proposition 4.3. Such properties were already known in the case k = 2, where F_{2} = G = ⌊(n + 1)/φ⌋ and x_{2} amounts to the Fibonacci word; see, for instance, Allouche and Shallit [2, Ex. 8.1.3]. The extended results to an arbitrary parameter k seem new.

All these relations between the functions F_{k} and the words x_{k} stem from the key Theorem 3.1 and its Corollary 3.2: F_{k} and their iterates admit Galois connections [7] (i.e., almost inverses) that can be simply expressed in terms of the length of τ_{k}-substituted prefixes of x_{k}. These lengths are called L_{k} here; see Proposition 2.3.

The words x_{k} are primarily considered here in order to study the monotonicity of the functions F_{k}. Nonetheless, several results on x_{k} are also of interest on their own. For example, for k ≥ 1 and n ≥ 0, we prove that there are more occurrences of the letter k among the first n letters of x_{k} than occurrences of the letter k + 1 among the first n letters of x_{k+1} (Theorem 7.2). Similarly, the letter 1 occurs more often among the first n letters of x_{k} than among the first n letters of x_{k+1} (Proposition 8.1). We denote the number of letters i among the prefix of x_{k} of length n by C_{k}^{(=i)}(n); see Section 4.

2Usually, the letter k is replaced by the letter 0 in the definition of τ_{k} and x_{k}. We choose the letter k in order to simplify some formulas and to extend the definition without modification to the case k = 1.

1.5 The Rocq formalization

All the results presented in this article have been formally certified using the Rocq proof assistant [19] (previously known as Coq). This implementation in Rocq is freely available [15]. Thanks to this Rocq formalization, we ensure precise definitions and statements while preventing any error during the corresponding proofs. It can hence serve as a reference for the interested reader. In particular, the recommended entry point to read alongside this article is

       https://github.com/letouzey/hofstadter_g/blob/main/Article1.v

The current article tries to be faithful to this formal work while staying readable by a large audience, at the cost of possible remaining mistakes during the transcription.

As a quick illustration, here is one possible Rocq encoding of the F_{k} function:^{3}

Fixpoint recf k p n : nat := match p with
| 0 => 0
| S p' => n - Nat.iter k (recf k p') (n-1)
end.
Definition f k n := recf k n n.

Note that Nat.iter k iterates a given function k times. This encoding departs slightly from the previous definition of F_{k}: in order to satisfy the Rocq constraints on recursive definitions, an extra parameter p is initialized to n and decreased in recursive calls. Then we proved that this Rocq definition fulfills the desired equation:^{4}

Lemma f_eqn : forall k n : nat, f k n = n - Nat.iter k (f k) (n-1).

In this setting, our main Theorem 1.1 has a very simple Rocq statement:^{5}

Theorem f_grows : forall k n, f k n <= f (k+1) n.

The provided Rocq files can be machine-checked again by any recent installation of Rocq; see the joint README file in the repository [15]. Since Sections 5 and 6 of this article involve real numbers, their corresponding Rocq files rely on the Rocq library Reals and its four logical axioms, in particular the axiom of excluded middle. All the rest of the formalization, including our key Theorem 1.1, has been performed within Rocq core logic, with no axiom. This fact can be checked via the Rocq command Print Assumptions on our theorems.

3See Definition f in the file GenG.v [15]. Faster implementations of F_{k} are also provided in the file Fast.v and proved equal with the version shown here.

4See Lemma f eqn and its proof in the file GenG.v [15]. Note that the Rocq subtraction on natural numbers of type nat is bounded by 0, for example 0-1 = 0. Therefore, the statement of f eqn holds both when n = 0 and when n ≠ 0.

5See Theorem f grows and its proof in the file WordGrowth.v [15].

1.6 Summary

After introducing some notation and basic properties in Section 2, we establish a key link between the functions F_{k} and words x_{k} in Section 3. In Section 4, we count some letters in prefixes of x_{k}. Section 5 presents some zeros of polynomials that are used in Section 6 when stating the infinitary behavior of our objects, i.e., when n → ∞. In particular, we present linear equivalents of F_{k} and a weak form of monotonicity for the family (F_{k}). Section 7 contains the promised full monotonicity proof for all n ≥ 0, at first for words, then functions, and various extensions are made or conjectured. Section 8 revisits the previous results, this time in terms of the number of occurrences of letters.

1.7 Related works

Various aspects of the functions F_{k} can be studied. We mention some of them, even if they do not seem to be connected to the monotonicity, which is the main focus of this article.

First, the case k = 2 has been well explored [5, 10]. However, the fact that F_{2} has an exact expression ⌊(n + 1)/φ⌋ is quite particular and too specific to draw general conclusions about all the other F_{k}.

A nice general fact about the functions F_{k} is that they can be presented as right shifts of digits when numbers n are written with the appropriate numerical representations. In particular, for k = 2, the corresponding numerical representation is the Zeckendorf decomposition, writing numbers as sums of distinct Fibonacci numbers. This can be extended to other values of k by changing the sequence used as the base for the decomposition, from Fibonacci numbers to a similar linear recurrence [17, 5, 14, 6, 3, 21]. In particular, Meek and Van Rees [17] focus on a slightly different family of functions, which can be written here as F_{k}(n + 1) − 1. If we denote these “shifted” functions by F̃_{k}, they verify the equations F̃_{k}(0) = 0 and F̃_{k}(n) = n − 1 − F̃_{k}^{k}(n − 1); note the extra −1 when compared to the equation of F_{k}. In any case, having a description of F_{k}(n) (or F̃_{k}(n)) in terms of a k-decomposition of n does not directly help for our monotonicity problem, since the k- and (k +1)-decompositions of n differ too much, just as a number tends to have very different base-2 and base-3 digits. The concept of k-decompositions is also related to the notions of substitutions and words that we exploit here directly.

As a final remark about F_{k}, note that F_{k} can also be presented as a companion infinite tree where the same pattern is continuously repeated: a binary node is followed on its right by k − 1 unary nodes. When the nodes of this tree are labelled by increasing numbers, in a breadth-first manner, left to right, then the node number n has F_{k}(n) as parent node. This was already described by Hofstadter [13]; also see the general introduction to the problem by the first author [16]. Here again, these alternative presentations of F_{k} do not seem to help concerning the monotonicity, with no direct relations between trees for k and for k + 1.

The sequences x_{k} defined in Section 1.3 can be considered as generalizations of the Fibonacci word. However, one can find many different “generalized Fibonacci” words in the literature, for example the k-bonacci words, which can be defined as fixed points of the morphism satisfying 1 ↦ k, i ↦ k(i − 1), for 2 ≤ i ≤ k [23], the fixed points of the morphisms 0 ↦ 0^{m}1^{n}, 1 ↦ 0, for positive integers m, n [2, Ex. 10.11.18], and other examples [18, 11, 12].

2 Notation and basic properties

We let ∂F_{k}^{j}(n) denote the difference F_{k}^{j}(n + 1) − F_{k}^{j}(n).

Proposition 2.1. For all j, k ≥ 1, the function F_{k}^{j} satisfies the following basic properties:

(a) F_{k}^{j}(1) = F_{k}^{j}(2) = 1,

(b) F_{k}^{j}(n) ≥ 1 whenever n ≥ 1,

(c) F_{k}^{j}(n) < n whenever n ≥ 2,

(d) we have ∂F_{k}(n) = 1 − ∂F_{k}^{k}(n − 1) for all n ≥ 1,

(e) hence ∂F_{k}^{j}(n) ∈ {0, 1} for all n ≥ 0,

(f) the function F_{k}^{j} is monotonically increasing and onto (but not one-to-one).

Proof. Direct use of the definition or easy induction on n.

For n ≥ 0, let x_{k}[0:n) = x_{k}[0]x_{k}[1] ⋯ x_{k}[n − 1] denote the prefix of x_{k} of length n. In particular, x_{k}[0:0) is the empty word, and |x_{k}[0:n)| = n, where |·| denotes the length of a word.

Note that x_{k} can also be seen as the fixed point of the substitution τ_{k}^{k−1}. Since τ_{k}^{k−1}(i) = k12 ⋯ (i − 1) for all 1 ≤ i ≤ k, this provides a decomposition of x_{k} into blocks delimited by the letter k (in red in Figure 1.2). The lengths of these blocks are the successive letters of x_{k}, and this gives us a convenient way to compute x_{k}. For instance, τ_{3}^{2}(3) = 312, then τ_{3}^{2}(312) = 312 3 31, etc.

Similarly, x_{k} is also the fixed point of τ_{k}^{k}. Since τ_{k}^{k}(i) = k12 ⋯ i for all 1 ≤ i ≤ k, this other decomposition is interesting for counting occurrences of the letter 1 in x_{k}, because 1 occurs only in the second position of each such block.

As an alternative way of computing x_{k}, note that its prefixes of the form τ_{k}^{j}(k) follow the following base cases and recursive rule.

Proposition 2.2. Let k ≥ 1. Then

τ_{k}^{j}(k) = \begin{cases}k12 ⋯ j, & if 0 ≤ j ≤ k; \\ τ_{k}^{j−1}(k) τ_{k}^{j−k}(k), & if j ≥ k. \end{cases}

Proof. We use induction on j. For j = 0, we have τ_{k}^{0}(k) = k. Otherwise, τ_{k}^{j}(k) = τ_{k}(τ_{k}^{j−1}(k)), and we use the induction hypothesis on j − 1. If j ≤ k, then

τ_{k}^{j}(k) = τ_{k}(τ_{k}^{j−1}(k)) = τ_{k}(k12 ⋯ (j − 1)) = k12 ⋯ j,

which also gives the recursive rule for j = k since k12 ⋯ (k − 1)k = τ_{k}^{k−1}(k)τ_{k}^{0}(k). If j > k, then j − 1 ≥ k, and

τ_{k}^{j}(k) = τ_{k}(τ_{k}^{j−1}(k)) = τ_{k}(τ_{k}^{j−1−1}(k)τ_{k}^{j−1−k}(k)) = τ_{k}^{j−1}(k)τ_{k}^{j−k}(k).

For k ≥ 1, an important counterpart to F_{k} is the function

L_{k} : ℕ → ℕ, n ↦ |τ_{k}(x_{k}[0:n))|.

Proposition 2.3. The lengths L_{k}(n) = |τ_{k}(x_{k}[0:n))| satisfy the following basic properties for all k ≥ 1 and j, n ≥ 0:

(a) the j-th iterate of L_{k} satisfies L_{k}^{j}(n) = |τ_{k}^{j}(x_{k}[0:n))|,

(b) L_{k}^{j}(0) = 0 and L_{k}^{j}(n + 1) = L_{k}^{j}(n) + |τ_{k}^{j}(x_{k}[n])|,

(c) L_{k}^{j}(1) = j + 1 when j ≤ k and L_{k}^{j}(1) = L_{k}^{j−1}(1) + L_{k}^{j−k}(1) when j ≥ k,

(d) the function L_{k}^{j} is strictly monotonically increasing over n,

(e) L_{k}^{j}(n) ≥ n, with equality only when j = 0 or n = 0,

(f) for n ≥ 1, the function j ↦ L_{k}^{j}(n) is strictly monotonically increasing over j.

Proof. First, τ_{k}(x_{k}[0:n)) is the prefix of x_{k} of length L_{k}(n). It is hence equal to x_{k}[0:L_{k}(n)). We claim that, more generally, τ_{k}^{j}(x_{k}[0:n)) is the prefix of x_{k} of length L_{k}^{j}(n) for all j ≥ 0. Since τ_{k}^{j}(x_{k}[0:n)) is a prefix of x_{k}, we only have to prove that its length is equal to L_{k}^{j}(n), and this follows inductively for j ≥ 1 from

|τ_{k}^{j}(x_{k}[0:n))| = |τ_{k}(τ_{k}^{j−1}(x_{k}[0:n)))| = |τ_{k}(x_{k}[0:L_{k}^{j−1}(n)))| = L_{k}(L_{k}^{j−1}(n)) = L_{k}^{j}(n).

Point (b) is a direct consequence of this more general claim. Point (c) directly comes from Proposition 2.2.

Now a key fact: for all finite words w, we have |w| ≤ |τ_{k}(w)|. This inequality is even strict when w is a non-empty prefix of x_{k}, since x_{k}[0] = k and |τ_{k}(k)| = 2. The remaining points are direct consequences of this key fact.

Proposition 2.4. For j ≥ 0 and k, m ≥ 1, there exists a unique n ≥ 1 such that L_{k}^{j}(n−1) < m ≤ L_{k}^{j}(n).

Proof. Standard consequence of L_{k}^{j}(0) = 0 and the strict monotonicity of L_{k}^{j}.

3 Relating functions and word lengths

We now establish that L_{k}^{j} allows expressing preimages of the function F_{k}^{j}.

Theorem 3.1. Let j ≥ 0 and k ≥ 1.

(a) For all n ≥ 1, we have

F_{k}^{−j}({n}) = (L_{k}^{j}(n − 1), L_{k}^{j}(n)] ∩ ℕ.

(b) Equivalently, for all m ≥ 1, we have

L_{k}^{j}(F_{k}^{j}(m) − 1) < m ≤ L_{k}^{j}(F_{k}^{j}(m)).  (3.1)

Proof. We first prove the equivalence of (a) and (b). The case (a) directly implies (b); just replace n by F_{k}^{j}(m). Now we prove the set equation in (a) assuming (b): If m ∈ F_{k}^{−j}({n}), then F_{k}^{j}(m) = n, and (3.1) becomes L_{k}^{j}(n − 1) < m ≤ L_{k}^{j}(n). Hence m is a natural number in the right interval. On the other hand, if m ∈ (L_{k}^{j}(n − 1), L_{k}^{j}(n)] ∩ ℕ, then Proposition 2.4 and (3.1) imply that F_{k}^{j}(m) = n, so m ∈ F_{k}^{−j}({n}). The two sets in (a) are hence equal.

We now prove the statement (b). The case k = 1 must be separately handled, since our general proof below requires the letters 1 and k to differ. Fortunately, when k = 1 we have L_{1}^{j}(n) = 2^{j}n and F_{1}^{j}(m) = ⌈m/2^{j}⌉, which easily resolves this case. We can also separately handle the case j = 0, which is obvious since both L_{k}^{0} and F_{k}^{0} are the identity functions.

From now on, we assume k ≥ 2 and prove the inequalities (3.1) for all j ≥ 1 by strong induction on m ≥ 1. For m ∈ {1, 2} and j ≥ 1, we have F_{k}^{j}(m) = 1 by Proposition 2.1, while L_{k}^{j}(0) = 0 and L_{k}^{j}(1) > L_{k}^{0}(1) = 1 by Proposition 2.3. Hence the desired inequalities hold in this case.

Let n ≥ 2, and assume that (3.1) holds for all 1 ≤ m ≤ n, j ≥ 1. We now prove the inequalities in (3.1) for m = n + 1, first in the case j = 1, and then for j ≥ 2. Case j = 1. We use the following instances of the induction hypothesis:

L_{k}(F_{k}(n) − 1) < n ≤ L_{k}(F_{k}(n)),  (3.2)
L_{k}^{k}(F_{k}^{k}(n) − 1) < n ≤ L_{k}^{k}(F_{k}^{k}(n)),  (3.3)
L_{k}^{k}(F_{k}^{k}(n − 1) − 1) < n − 1 ≤ L_{k}^{k}(F_{k}^{k}(n − 1)).  (3.4)

Also recall from Proposition 2.1 that

F_{k}(n + 1) − F_{k}(n) = 1 − (F_{k}^{k}(n) − F_{k}^{k}(n − 1))

and F_{k}^{k}(n) − F_{k}^{k}(n − 1) is either 0 or 1. We separately handle these two possible differences. Case j = 1, F_{k}^{k}(n) = F_{k}^{k}(n − 1). If F_{k}^{k}(n) = F_{k}^{k}(n − 1), then F_{k}(n + 1) = F_{k}(n) + 1. From (3.2) and the strict monotonicity of L_{k} (Proposition 2.3), we get

n ≤ L_{k}(F_{k}(n)) < L_{k}(F_{k}(n) + 1) = L_{k}(F_{k}(n + 1)).

Hence the right inequality in (3.1) holds for m = n+1, j = 1. We claim that L_{k}(F_{k}(n)) = n. If this were not the case, then (3.2) would give L_{k}(F_{k}(n) − 1) ≤ n − 1 < n < L_{k}(F_{k}(n)). For the words corresponding to these lengths, this would imply that x_{k}[n − 1]x_{k}[n] is a subword of τ_{k}(x_{k}[F_{k}(n) − 1]), and in particular that |τ_{k}(x_{k}[F_{k}(n) − 1])| ≥ 2. This could only happen when x_{k}[F_{k}(n) − 1] = k, and thus x_{k}[n] = 1. From F_{k}^{k}(n) = F_{k}^{k}(n − 1), (3.3) and (3.4), we get L_{k}^{k}(F_{k}^{k}(n) − 1) ≤ n − 2 < n − 1 < L_{k}^{k}(F_{k}^{k}(n)), and hence x_{k}[n − 2]x_{k}[n − 1] is a subword of the block τ_{k}^{k}(x_{k}[F_{k}^{k}(n) − 1]). Recall that the letter 1 occurs in this kind of block only at the second position. But here, either x_{k}[n] is still in the block, but at least in third position, or it starts the next block, and hence x_{k}[n] = k. Both cases are incompatible with x_{k}[n] = 1. Therefore, we have L_{k}(F_{k}(n)) = n. Hence

L_{k}(F_{k}(n + 1) − 1) = L_{k}(F_{k}(n)) = n < n + 1,

and also the left inequality in (3.1) holds here for m = n + 1, j = 1. Case j = 1, F_{k}^{k}(n) = F_{k}^{k}(n − 1) + 1. If F_{k}^{k}(n) − F_{k}^{k}(n − 1) = 1, then F_{k}(n + 1) = F_{k}(n). In this case, the left inequality in (3.1) is clear from (3.2):

L_{k}(F_{k}(n + 1) − 1) = L_{k}(F_{k}(n) − 1) < n < n + 1.

From (3.3) and (3.4), we deduce that L_{k}^{k}(F_{k}^{k}(n − 1)) = n − 1. Hence, x_{k}[n − 1]x_{k}[n] starts a new τ_{k}^{k} block, and thus x_{k}[n − 1]x_{k}[n] = k1. This means that the left inequality of (3.2) is actually strict here, because the letter 1 cannot start the word τ_{k}(x_{k}[F_{k}(n)]). So finally

n < L_{k}(F_{k}(n)) = L_{k}(F_{k}(n + 1)),

and we have finished the proof of (3.1) for m = n + 1, j = 1, in all possible cases. Case j ≥ 2. It remains to prove (3.1) for m = n + 1 and j ≥ 2. Since 1 ≤ F_{k}(n + 1) ≤ n by Proposition 2.1, the induction hypothesis holds for m = F_{k}(n + 1) and j − 1. Hence

L_{k}^{j−1}(F_{k}^{j}(n + 1) − 1) ≤ F_{k}(n + 1) − 1 ≤ F_{k}(n + 1) ≤ L_{k}^{j−1}(F_{k}^{j}(n + 1)).

Applying L_{k}, which preserves these inequalities by monotonicity (Proposition 2.3), gives

L_{k}^{j}(F_{k}^{j}(n + 1) − 1) ≤ L_{k}(F_{k}(n + 1) − 1) ≤ L_{k}(F_{k}(n + 1)) ≤ L_{k}^{j}(F_{k}^{j}(n + 1)).

Finally, we can use (3.1), which we proved for m = n + 1 and j = 1 above, in the middle:

L_{k}^{j}(F_{k}^{j}(n + 1) − 1) ≤ L_{k}(F_{k}(n + 1) − 1) < n + 1 ≤ L_{k}(F_{k}(n + 1)) ≤ L_{k}^{j}(F_{k}^{j}(n + 1)).

Therefore, (3.1) indeed holds for m = n + 1 and all j ≥ 1. Thus, by induction, (3.1) holds for all m ≥ 1, which concludes the proof of the theorem.

In particular, we have F_{k}^{j}(L_{k}^{j}(n)) = n for all k ≥ 1 and j, n ≥ 0. Moreover, L_{k}^{j}(n) is the largest element of F_{k}^{−j}({n}) while L_{k}^{j}(n − 1) + 1 is the smallest one (for n > 0), and these extrema may coincide. In particular, this is always the case when j = 0 and quite frequently when j = 1 and k > 1; see Proposition 6.5 for a study of this ratio.

The relationship between F_{k}^{j} and L_{k}^{j} can also be formulated as a Galois connection [7].

Corollary 3.2. For all j ≥ 0 and k ≥ 1, the functions F_{k}^{j} and L_{k}^{j} form a Galois connection between ℕ and itself (with F_{k}^{j} as left adjoint and L_{k}^{j} as right adjoint). Indeed, for all m, n ≥ 0 we have F_{k}^{j}(n) ≤ m if and only if n ≤ L_{k}^{j}(m). Moreover, this Galois connection is said to be a Galois insertion because F_{k}^{j} ∘ L_{k}^{j} = id.

Proof. The case n = 0 is obvious. For n ≥ 1, if F_{k}^{j}(n) ≤ m, then n ≤ L_{k}^{j}(F_{k}^{j}(n)) ≤ L_{k}^{j}(m) by Theorem 3.1 and the monotonicity of L_{k}^{j}. Conversely, if n ≤ L_{k}^{j}(m), then F_{k}^{j}(n) ≤ F_{k}^{j}(L_{k}^{j}(m)) by monotonicity of L_{k}^{j} and F_{k}^{j}(L_{k}^{j}(m)) = m as seen above.

Note that Proposition 4.2 below gives a nice expression of L_{k}(n) as n + F_{k}^{k−1}(n). Hence

L_{k}(F_{k}(n)) = F_{k}(n) + F_{k}^{k}(n) = n + 1 − ∂F_{k}(n) ∈ {n, n + 1}.

4 Counting letters

We now express the number of occurrences for the letters 1, …, k in prefixes of x_{k}. Thanks to Theorem 3.1, this relates them to functions F_{k} in various ways.

Let C_{k}^{(P)}(n) denote the number of letters satisfying the predicate P in the prefix x_{k}[0:n). More formally,

C_{k}^{(P)}(n) = #{0 ≤ j < n : P (x_{k}[j])}.

In particular, we use the expressions

• C_{k}^{(=i)}(n) for counting the occurrences of a specific letter i,

• C_{k}^{(>i)}(n) = C_{k}^{(=i+1)}(n) + ⋯ + C_{k}^{(=k)}(n) for counting all letters strictly greater than i.

Proposition 4.1. For all k ≥ 1 and n ≥ 0, we have

F_{k}^{k−1}(n) = C_{k}^{(=k)}(n),  (4.1)
F_{k}^{j}(n) = C_{k}^{(>j)}(n)  for all 0 ≤ j < k,  (4.2)
F_{k}^{k+i−1}(n) = C_{k}^{(=i)}(n + i) for all 1 ≤ i < k.  (4.3)

Proof. We can use the same counting technique to prove each of these three equations.

For Equation (4.1), we already mentioned that x_{k} can be seen as a succession of “blocks” τ_{k}^{k−1}(i) = k1 ⋯ (i − 1), each one containing k only as first letter. For a given m ≥ 0, the letter x_{k}[m] belongs to one of these blocks, say the p-th one (counting from p = 1 for the first block). We hence have p occurrences of the letter k in x_{k}[0] ⋯ x_{k}[m], so C_{k}^{(=k)}(m + 1) = p. Also note that the first p blocks have a total length of |τ_{k}^{k−1}(x_{k}[0:p))| = L_{k}^{k−1}(p). So L_{k}^{k−1}(p) is also the first index in the (p + 1)-st block, and hence L_{k}^{k−1}(p) > m. Similarly L_{k}^{k−1}(p − 1) is the first index of the p-th block, so all in all

L_{k}^{k−1}(p − 1) ≤ m < L_{k}^{k−1}(p).

After substituting p and setting n = m + 1, we obtain that for all n > 0 we have

L_{k}^{k−1}(C_{k}^{(=k)}(n) − 1) < n ≤ L_{k}^{k−1}(C_{k}^{(=k)}(n)).

By Theorem 3.1 and Proposition 2.4, this implies F_{k}^{k−1}(n) = C_{k}^{(=k)}(n) for all k, n ≥ 1. Moreover, this identity trivially holds for n = 0 as well.

For Equation (4.2), we generalize the previous counting technique. For 0 ≤ j < k and a letter 1 ≤ i ≤ k, the word τ_{k}^{j}(i) starts with exactly one letter strictly greater than j, while the rest of this word consists of letters less than or equal to j. Indeed, either i + j ≤ k and τ_{k}^{j}(i) = i + j > j, or i + j ≥ k and τ_{k}^{j}(i) = τ_{k}^{i+j−k}(k) = k1 ⋯ (i + j − k) with i + j − k ≤ j. Just as before, we deduce that

L_{k}^{j}(C_{k}^{(>j)}(n) − 1) < n ≤ L_{k}^{j}(C_{k}^{(>j)}(n))

for all 0 ≤ j < k and n > 0. As earlier, this allows establishing F_{k}^{j}(n) = C_{k}^{(>j)}(n) for all 0 ≤ j < k and n > 0. Once again, this identity also holds for n ≥ 0.

Finally, we use yet another instance of the same technique for proving Equation (4.3). Consider 1 ≤ i < k. For all letters 1 ≤ j ≤ k the words τ_{k}^{k+i−1}(j) contain the letter i only at the (i+1)-st position. Indeed, these words can also be written τ_{k}^{j+i−1}(k) (since τ_{k}^{k−j}(j) = k), so they all admit τ_{k}^{i}(k) = k1 ⋯ i as a common prefix, possibly followed first by letters greater than i and then by new blocks no larger than k1 ⋯ (i − 1). For similar reasons as before, we hence have

L_{k}^{k+i−1}(C_{k}^{(=i)}(n) − 1) < n − i ≤ L_{k}^{k+i−1}(C_{k}^{(=i)}(n))

for all n ≥ i + 1. So for all 1 ≤ i < k and n ≥ 0, we have F_{k}^{k+i−1}(n) = C_{k}^{(=i)}(n + i).

Actually, Equation (4.1) can also be deduced from Equation (4.2) in the particular case j = k − 1, since C_{k}^{(>k−1)} = C_{k}^{(=k)}. Also note that Equation (4.3) could be extended to the case i = 0 if we replace the letter k by 0 in the substitution τ_{k} and its fixed point x_{k}.

We can now give an interesting alternative expression for L_{k}(n) (which is the largest element of F_{k}^{−1}({n}) by Theorem 3.1).

Proposition 4.2. For all k ≥ 1 and n ≥ 0,

L_{k}(n) = n + C_{k}^{(=k)}(n) = n + F_{k}^{k−1}(n).

Proof. We have |τ_{k}(k)| = 2 while |τ_{k}(i)| = 1 for the other letters i ≠ k. Hence

L_{k}(n) = 2 C_{k}^{(=k)}(n) + C_{k}^{(≠k)}(n) = n + C_{k}^{(=k)}.

Finally, Equation (4.1) leads to the last equality.

By Equation (4.2), we can also express the number of occurrences of a specific letter 1 ≤ j < k via the difference between C_{k}^{(>j−1)} and C_{k}^{(>j)}. Hence for 1 ≤ j < k and n ≥ 0

F_{k}^{j−1}(n) − F_{k}^{j}(n) = C_{k}^{(>j−1)}(n) − C_{k}^{(>j)}(n) = C_{k}^{(=j)}(n).  (4.4)

In particular, we obtain the following proposition.

Proposition 4.3. For k > 1 and n ≥ 0,

F_{k}(n) = n − C_{k}^{(=1)}(n) = C_{k}^{(≠1)}(n).

Hence ∂F_{k}(n) is 0 if and only if x_{k}[n] = 1, and 1 otherwise.

Proof. Direct use of the previous equation in the particular case j = 1. Alternatively, one may use Equation (4.3) for i = 1, and then the recursive definition of F_{k}.

Afterwards, we get F_{k}(n + 1) − F_{k}(n) = 1 − (C_{k}^{(=1)}(n + 1) − C_{k}^{(=1)}(n)), which is 0 if and only if x_{k}[n] = 1 and 1 otherwise.

This important link between ∂F_{k} and x_{k} helps us to transfer many properties from one to the other. In particular, ∂F_{k} cannot have two consecutive zeros, and it admits up to k consecutive ones but not k + 1.

Now let us describe the letters of x_{k} in terms of differences ∂F_{k}^{j}(n). Recall from Proposition 2.1 that these differences are always either 0 or 1. Of course, ∂F_{k}^{0}(n) = 1 and ∂F_{k}^{j}(0) = 1. Now, for a non-zero n, we have F_{k}^{j}(n) = 1 when j is large enough, in particular for j ≥ n−1. Indeed, on a non-zero argument, F_{k} either returns 1 or removes at least one from its argument, and this is iterated here j times. As a consequence, we always have ∂F_{k}^{n}(n) = 0 when n > 0. Moreover, if for some j, we have ∂F_{k}^{j}(n) = 0, then ∂F_{k}^{j+1}(n) = 0 as well. Conversely, if ∂F_{k}^{j}(n) = 1, then ∂F_{k}^{j−1}(n) = 1. Hence for all k, n ≥ 1, the sequence (∂F_{k}^{j}(n))_{j∈ℕ} consists of a block of ones followed by an infinity of zeros. Actually, the letters of x_{k} indicate how deep to dive in these differences to find a first zero (or give up after k − 1 attempts).

Proposition 4.4. Let 1 ≤ j < k, n ≥ 0. We have x_{k}[n] = j if and only if both ∂F_{k}^{j−1}(n) = 1 and ∂F_{k}^{j}(n) = 0. Moreover, for k ≥ 1, we have x_{k}[n] = k if and only if ∂F_{k}^{k−1}(n) = 1. (In the latter case, ∂F_{k}^{k}(n) could be either 0 or 1.)

Proof. First, this statement is obvious for k = 1. We now assume that k > 1. By subtracting Equation (4.4) for n + 1 and n, we obtain for each 1 ≤ j < k that

∂F_{k}^{j−1}(n) − ∂F_{k}^{j}(n) = C_{k}^{(=j)}(n + 1) − C_{k}^{(=j)}(n).

This amounts to 1 if and only if x_{k}[n] = j, and 0 otherwise. So in particular for each i < x_{k}[n] we have ∂F_{k}^{i−1}(n) = ∂F_{k}^{i}(n). Meanwhile, we just noticed in Proposition 4.3 that ∂F_{k}(n) = 0 if and only if x_{k}[n] = 1. Write ℓ = x_{k}[n]. Three situations may occur:

• Either ℓ = 1, and we directly have ∂F_{k}(n) = 0 and ∂F_{k}^{0}(n) = 1.

• Or 1 < ℓ < k and ∂F_{k}(n) = 1. We can propagate ∂F_{k}^{i}(n) = 1 for all i < ℓ and finish with ∂F_{k}^{ℓ−1}(n) − ∂F_{k}^{ℓ}(n) = 1. Hence ∂F_{k}^{ℓ}(n) = 0.

• Lastly, if ℓ = k, then the propagation ∂F_{k}^{i}(n) = 1 goes up to i ≤ k − 1. Hence the desired statement follows.

5 Related polynomials and algebraic integers

We now introduce two families of polynomials whose positive zeros appear as average slopes for F_{k} and L_{k} and letter frequencies for x_{k} (Section 6).

Definition 5.1. For k ≥ 1, we define P_{k}(X) = X^{k} +X −1 and Q_{k}(X) = X^{k} −X^{k−1} −1. We let α_{k} (and β_{k} respectively) be the unique positive zero of P_{k} (and Q_{k} respectively). Note that β_{k} = 1/α_{k}.

A more complete investigation of these polynomials can be found in Selmer [20] (where the polynomials X^{k} ± (X + 1) lead to P_{k}(−X)) and Dilcher [4]. We now state the elementary results needed in the rest of our work. In particular, for k ≥ 1, the polynomial P_{k} is strictly increasing on ℝ_{+} and admits exactly one zero there. This zero α_{k} clearly satisfies \frac{1}{2} ≤ α_{k} < 1. Moreover the polynomial P_{k} is the negation of the reciprocal polynomial of Q_{k}, i.e., P_{k}(X) = −X^{k} Q_{k}(1/X) (and vice versa). As a consequence, the zeros of P_{k} are the inverse of the zeros of Q_{k} and vice versa. In particular β_{k} = 1/α_{k} is indeed the unique zero of P_{k} in ℝ_{+} and furthermore 1 < β_{k} ≤ 2.

Figure 5.1 gives approximate values for the first α_{k} and β_{k}. In particular, note that β_{1} = 2 and β_{2} is the golden ratio φ = \frac{1+\sqrt{5}}{2}. Thanks to the rational zero theorem, one can easily show that α_{k} and β_{k} are irrational for k ≥ 2.

\begin{aligned}α_{1} & = 0.5 \\ α_{2} & = 0.6180339887498948 … \\ α_{3} & = 0.6823278038280193 … \\ α_{4} & = 0.7244919590005157 … \\ α_{5} & = 0.7548776662466925 … \\ α_{6} & = 0.7780895986786012 … \end{aligned} \begin{aligned}β_{1} & = 2 \\ β_{2} & = 1.618033988749895 … \\ β_{3} & = 1.465571231876768 … \\ β_{4} & = 1.380277569097614 … \\ β_{5} & = 1.324717957244746 … \\ β_{6} & = 1.285199033245349 … \end{aligned}

Figure 5.1: The first α_{k} and β_{k}, positive zeros of X^{k} + X − 1 and X^{k} − X^{k−1} − 1.

Proposition 5.2. The sequence (α_{k})_{k∈ℕ_{+}} is strictly increasing while (β_{k})_{k∈ℕ_{+}} is strictly decreasing. Moreover, for k ≥ 1, we have 1+ \frac{1}{k} ≤ β_{k} ≤ 1+ \frac{1}{\sqrt{k}} or equivalently \sqrt{k} ≤ β_{k}^{k−1} ≤ k. Hence the (β_{k}) sequence converges to 1, as well as the (α_{k}) sequence. Actually, the following asymptotic expressions hold for k → ∞:

α_{k} = 1 − \frac{ln k}{k} + o(\frac{ln k}{k} ),  (5.1)
β_{k} = 1 + \frac{ln k}{k} + o(\frac{ln k}{k} ).  (5.2)

Proof. Let k ≥ 1. Suppose α_{k+1} ≤ α_{k}. Since α_{k} and α_{k+1} are in (0, 1), we would have α_{k+1}^{k+1} = α_{k+1}^{k}α_{k+1} < α_{k+1}^{k} ≤ α_{k}^{k}, leading to 0 = P_{k+1}(α_{k+1}) < P_{k}(α_{k}) = 0, a contradiction. Hence (α_{k}) is strictly increasing and (β_{k}) = (α_{k}^{−1}) is strictly decreasing.

Now Q_{k}(β_{k}) = 0 can be reformulated as β_{k}^{k−1}(β_{k} − 1) = 1 and hence

α_{k}^{k−1} = β_{k}^{−(k−1)} = β_{k} − 1.  (5.3)

This provides the equivalence between \sqrt{k} ≤ β_{k}^{k−1} ≤ k and 1 + \frac{1}{k} ≤ β_{k} ≤ 1 + \frac{1}{\sqrt{k}}. For proving the lower bound \sqrt{k} ≤ β_{k}^{k−1}, it is sufficient to note that

1 + β_{k} + ⋯ + β_{k}^{k−1} = \frac{β_{k}^{k} − 1}{β_{k} − 1} = \frac{β_{k}^{k−1}}{β_{k}^{−(k−1)}} = β_{k}^{2(k−1)}.  (5.4)

Each term on the left of Equation (5.4) is 1 or larger, so k ≤ β_{k}^{2(k−1)}, hence the desired lower bound. For the upper bound β_{k}^{k−1} ≤ k, we divide by β_{k}^{k−1} in Equation (5.4) and obtain

β_{k}^{k−1} = \frac{β_{k}^{2(k−1)}}{β_{k}^{k−1}} = \frac{1}{β_{k}^{k−1}} + ⋯ + \frac{β_{k}^{k−1}}{β_{k}^{k−1}} = α_{k}^{k−1} + ⋯ + α_{k} + 1 ≤ k.

The two asymptotic expressions (5.1) and (5.2) are equivalent: considering the multiplicative inverse of any of these expressions leads to the other one. An approximation related to (5.1) appears in Selmer [20, Eq. 4.4] but without further explanation, while (5.2) is a direct consequence of Dilcher [4, Lem. 3]. Alternatively, we give here a simple direct proof of (5.1). For k ≥ 1, we consider the function h_{k}(x) = \sqrt[k]{1 − x} and note that α_{k} is a fixed point of h_{k}. It could be proved that iterating h_{k} on any initial point in (0, 1) converges to α_{k}, but here it suffices to use a few initial terms of such a sequence, namely u_{0} = 1 − 1/e and u_{1} = h_{k}(u_{0}) and u_{2} = h_{k}(u_{1}) and u_{3} = h_{k}(u_{2}). For these values, it is straightforward to compute

u_{1} = e^{−1/k} = 1 − \frac{1}{k} + o(\frac{1}{k}),
u_{2} = 1 − \frac{ln k}{k} + o(\frac{1}{k}),
u_{3} = 1 − \frac{ln k}{k} + \frac{ln ln k}{k} + o(\frac{1}{k}).

Meanwhile, a basic study of the function h_{k} ensures that u_{0} < u_{2} < α_{k} < u_{3} < u_{1} when k ≥ 3. The desired expression (5.1) follows by weakening the previous asymptotic expressions for both u_{2} and u_{3} to 1 − ln k/k + o(ln k/k).

6 Infinitary behavior

For each k ≥ 1, the substitution τ_{k} is a primitive morphism [1]; i.e., there exists an exponent p ≥ 1 such that for all letters 1 ≤ i, j ≤ k, the letter i occurs in τ_{k}^{p}(j). Here, the first adequate exponent is p = 2k − 2. Indeed, τ_{k}^{2k−2}(j) admits τ_{k}^{k−1}(k) = k1 ⋯ (k − 1) as a prefix because τ_{k}^{k−1}(j) has k as first letter. Since x_{k} is the fixed point of a primitive morphism, each letter i, 1 ≤ i ≤ k, has a frequency, which we denote by freq_{k}(i). More precisely, the limit freq_{k}(i) = lim_{n→∞} \frac{1}{n}C_{k}^{(=i)}(n) exists, we have 0 < freq_{k}(i) ≤ 1, and there exists a formula for computing it [2, Thm. 8.4.7]. Here, an easier approach for computing freq_{k}(i) is to consider F_{k}.

Theorem 6.1. For j ≥ 0 and k ≥ 1, the following limits exist and have the given values, where α_{k} and β_{k} come from Definition 5.1:

lim_{n→∞} \frac{1}{n}F_{k}^{j}(n) = α_{k}^{j},
lim_{n→∞} \frac{1}{n}L_{k}^{j}(n) = β_{k}^{j},
freq_{k}(i) = α_{k}^{k+i−1},  for 1 ≤ i < k,
freq_{k}(k) = α_{k}^{k−1} = β_{k} − 1.

Proof. Recall from Proposition 4.3 that for k > 1 and n ≥ 0, we have F_{k}(n) = n − C_{k}^{(=1)}(n). Hence the limit lim_{n→∞} \frac{1}{n}F_{k}(n) exists as well^{6} and is 1 − freq_{k}(1). In the case k = 1, we have F_{1}(n) = ⌈n/2⌉. Hence lim_{n→∞} \frac{1}{n}F_{1}(n) = \frac{1}{2}.

Now that \frac{1}{n}F_{k}(n) is known to converge to some finite limit ℓ, computing this limit is quite straightforward. Indeed, the recursive equation of F_{k} can be reformulated as

\frac{F_{k}(n)}{n} = 1 − \frac{F_{k}(F_{k}^{k−1}(n − 1))}{F_{k}^{k−1}(n − 1)} ⋯ \frac{F_{k}(n − 1)}{n − 1} \frac{n − 1}{n}

for n > 1. Each fraction can be shown to converge to ℓ, except \frac{n−1}{n}, which tends to 1. Hence ℓ = 1 − ℓ^{k} and obviously ℓ is a nonnegative real number. Hence ℓ = α_{k}. As a consequence, for k ≥ 2, the frequency freq_{k}(1) is 1 − α_{k} = α_{k}^{k} (and 1 when k = 1). The same telescoping technique gives lim_{n→∞} \frac{1}{n}F_{k}^{j}(n) = α_{k}^{j}.

Concerning L_{k}^{j}, a consequence of Theorem 3.1 is F_{k}^{j}(L_{k}^{j}(n)) = n. Hence

\frac{L_{k}^{j}(n)}{n} = (\frac{F_{k}^{j}(L_{k}^{j}(n))}{L_{k}^{j}(n)})^{−1}.

Since L_{k}^{j}(n) ≥ n, this implies that \frac{1}{n}L_{k}^{j}(n) converges, and its limit is α_{k}^{−j} = β_{k}^{j}.

For the frequency of the letter k, Equation (4.1) implies that freq_{k}(k) = α_{k}^{k−1}, which is also β_{k} − 1 by Equation (5.3). And for the frequencies of the other letters 1 ≤ i < k, one may exploit either Equation (4.4) or Equation (4.3). For instance, the former leads to

freq_{k}(i) = α_{k}^{i−1} − α_{k}^{i} = α_{k}^{i−1}(1 − α_{k}) = α_{k}^{k+i−1}.

In particular, this subsumes the case i = 1 seen earlier. Finally, one may check that the sum of all these frequencies, from α_{k}^{k−1} (letter k) to α_{k}^{2k−2} (letter k − 1), is of course 1.

6Surprisingly, we have not found any obvious methods for proving this convergence of \frac{1}{n}F_{k}(n) directly from the recursive definition of F_{k}, without using this “detour” via words.

Definition 6.2. For two functions f, g : ℕ → ℕ, we say that f is ultimately smaller than g and write f <_{∞} g when there exists N such that f(n) < g(n) for all n ≥ N.

Corollary 6.3. When α_{k}^{j} < α_{k′}^{j′} for some k, k′ ≥ 1 and j, j′ ≥ 0, then F_{k}^{j} <_{∞} F_{k′}^{j′}.

Proof. Theorem 6.1 gives lim_{n→∞} \frac{1}{n}F_{k}^{j}(n) = α_{k}^{j} < α_{k′}^{j′} = lim_{n→∞} \frac{1}{n}F_{k′}^{j′}(n). For n large enough, both sides become close enough to their limits, so there must exists N ≥ 1 such that n ≥ N implies \frac{1}{n}F_{k}^{j}(n) < \frac{1}{n}F_{k′}^{j′}(n) and hence F_{k}^{j}(n) < F_{k′}^{j′}(n).

Corollary 6.4. For k ≥ 1, we have F_{k} <_{∞} F_{k+1}, F_{k}^{k} >_{∞} F_{k+1}^{k+1} and F_{k}^{k+1} >_{∞} F_{k+1}^{k+2}. More generally, for j ≥ 0 and k ≥ 1:

(a) we have F_{k}^{k+j} >_{∞} F_{k+1}^{k+j+1} when α_{k} ≥ \frac{j}{j+1} (hence in particular when k ≥ j^{2});

(b) we have F_{k}^{k+j} <_{∞} F_{k+1}^{k+j+1} when α_{k+1} ≤ \frac{j}{j+1} (hence in particular when 1 ≤ k < j).

Proof. All these facts are obtained by the previous corollary; we just have to compare the corresponding average slopes. For F_{k} <_{∞} F_{k+1}, Proposition 5.2 directly gives α_{k} < α_{k+1}. For F_{k}^{k} >_{∞} F_{k+1}^{k+1}, we have α_{k}^{k} = 1 − α_{k} > 1 − α_{k+1} = α_{k+1}^{k+1}. Now, for F_{k}^{k+1} >_{∞} F_{k+1}^{k+2}, we have

α_{k}^{k+1} − α_{k+1}^{k+2} = (1 − α_{k})α_{k} − (1 − α_{k+1})α_{k+1} = (α_{k+1} − α_{k})(α_{k} + α_{k+1} − 1) > 0

since \frac{1}{2} ≤ α_{k} < α_{k+1}. More generally, let j ≥ 0. As before,

α_{k}^{k+j} − α_{k+1}^{k+j+1} = (1 − α_{k})α_{k}^{j} − (1 − α_{k+1})α_{k+1}^{j}.

The function (1 − X)X^{j} is strictly increasing between 0 and \frac{j}{j+1} and strictly decreasing afterwards. Since we always have α_{k} < α_{k+1}, then α_{k}^{k+j} − α_{k+1}^{k+j+1} > 0 at least when α_{k} ≥ \frac{j}{j+1} or equivalently when β_{k} ≤ 1 + \frac{1}{j}. Thanks to the bounds in Proposition 5.2, this happens at least when \sqrt{k} ≥ j, i.e., k ≥ j^{2}. Conversely, α_{k}^{k+j} − α_{k+1}^{k+j+1} < 0 at least when α_{k+1} ≤ \frac{j}{j+1}, for which a sufficient condition is 1 ≤ k < j, still thanks to the bounds in Proposition 5.2.

Corollary 6.4 is to be compared with the results of the next section, for instance Theorem 7.4: The latter gives only non-strict inequalities, but for all n ≥ 0, while here we have proved strict inequalities, but only when n is larger than some bounds. Moreover, we do not have explicit estimates for these bounds for the moment.

As a related matter, we can estimate the ratio of numbers having unique preimages by F_{k}.

Proposition 6.5. For k ≥ 1, n ≥ 0, let us call U_{k}(n) = #{0 ≤ j < n : |F_{k}^{−1}({j})| = 1}. Then, for n > 0, we have

U_{k}(n) = 2n − 1 − L_{k}(n − 1) = n − F_{k}^{k−1}(n − 1),

and hence

lim_{n→∞} \frac{1}{n}U_{k}(n) = 1 − α_{k}^{k−1} = 2 − β_{k}.

Proof. Let n > 0. We already know from Theorem 3.1 and Proposition 4.2 that the largest element of F_{k}^{−1}({n − 1}) is L_{k}(n − 1) = n − 1 + F_{k}^{k−1}(n − 1). There are U_{k}(n) numbers between 0 and n − 1 with a unique preimage, and the other n − U_{k}(n) numbers have exactly two preimages; see the discussion after Proposition 4.3. By counting the cardinality of F_{k}^{−1}({0, …, n − 1}), we obtain

U_{k}(n) + 2(n − U_{k}(n)) = 1 + L_{k}(n − 1) = n + F_{k}^{k−1}(n − 1).

Combined with Theorem 6.1, this leads to the desired equations and limits.

In particular, for k = 1 and n > 0 we get U_{1}(n) = 1. Indeed, since F_{1}(n) = ⌈\frac{n}{2}⌉, the only number with a unique preimage by F_{1} is 0. Then \frac{1}{n}U_{k}(n) tends to 0.3819 … for k = 2, to 0.5344 … for k = 3, and to 0.6197 … for k = 4, and these limits tend to 1 as k grows.

7 Monotonicity over the parameter k

This section studies the monotonicity of L_{k} and F_{k} when the parameter k varies. In all this section, we compare functions via pointwise order: an inequality such as F_{k} ≤ F_{k+1} means that F_{k}(n) ≤ F_{k+1}(n) for all points n ≥ 0. As such, the results here are quite stronger than the ones of the previous section about the infinitary behavior, i.e., when n is large enough.

First, we state a nice duality between functions F_{k}^{j} and L_{k}^{j} with respect to this pointwise order, extending the results of Section 3. Thanks to this, all the following technical lemmas about L_{k} have immediate counterparts for F_{k}.

Proposition 7.1. For j, j′ ≥ 0 and k, k′ ≥ 1, we have L_{k}^{j} ≤ L_{k′}^{j′} if and only if F_{k′}^{j′} ≤ F_{k}^{j}. Furthermore, we can be more precise concerning the relative positions where these inequalities occur. For n ≥ 0, we have

(a) L_{k}^{j}(n) ≤ L_{k′}^{j′}(n) if and only if F_{k′}^{j′}(m) ≤ F_{k}^{j}(m), with m = L_{k}^{j}(n),

(b) L_{k}^{j}(n) < L_{k′}^{j′}(n) if and only if F_{k′}^{j′}(m) < F_{k}^{j}(m), with m = L_{k′}^{j′}(n),

(c) L_{k}^{j}(m) ≤ L_{k′}^{j′}(m) for m = F_{k}^{j}(n) implies that F_{k′}^{j′}(n) ≤ F_{k}^{j}(n),

(d) F_{k}^{j}(n) < F_{k′}^{j′}(n) implies that L_{k′}^{j′}(m) < L_{k}^{j}(m) for m = F_{k′}^{j′}(n).

Proof. First, the fact that L_{k}^{j} ≤ L_{k′}^{j′} implies F_{k′}^{j′} ≤ F_{k}^{j} is a consequence of point (c), while point (a) implies the other direction. Also note that (b) is a contrapositive version of (a), and the same for (d) and (c).

For proving point (a), let n ≥ 0. Then L_{k}^{j}(n) ≤ L_{k′}^{j′}(n) is equivalent to F_{k′}^{j′}(L_{k}^{j}(n)) ≤ n by Corollary 3.2, and we have n = F_{k}^{j}(L_{k}^{j}(n)) by Theorem 3.1.

For point (c), we use that F_{k′}^{j′}(n) ≤ F_{k}^{j}(n) is equivalent to n ≤ L_{k′}^{j′}(F_{k}^{j}(n)) by Corollary 3.2. By Theorem 3.1 (or trivially when n = 0), we have n ≤ L_{k}^{j}(F_{k}^{j}(n)), and thus n ≤ L_{k′}^{j′}(F_{k}^{j}(n)) when L_{k}^{j}(F_{k}^{j}(n)) ≤ L_{k′}^{j′}(F_{k}^{j}(n)).

Let us now study the ordering of the functions L_{k}^{j}. Note first that

|τ_{k}^{k}(i)| = i + 1 = |τ_{k}^{k−1}(i)| + 1 for all 1 ≤ i ≤ k.

For all k ≥ 1, n ≥ 0, this implies that L_{k}^{k}(n) = L_{k}^{k−1}(n) + n and thus

L_{k+1}^{k+1}(n) − L_{k}^{k}(n) = L_{k+1}^{k}(n) − L_{k}^{k−1}(n).  (7.1)

One of our main results is that the sequence of functions (L_{k}) is monotonic, which we prove here by mutual induction with another property comparing iterations L_{k}^{j} and L_{k+1}^{j+1}.

Theorem 7.2. For all k, n ≥ 1, 0 ≤ j ≤ k, we have

L_{k}(n) ≥ L_{k+1}(n), i.e., C_{k}^{(=k)}(n) ≥ C_{k+1}^{(=k+1)}(n),  (7.2)
L_{k}^{j}(n) < L_{k+1}^{j+1}(n).  (7.3)

Proof. Let k ≥ 1. Since x_{k}[0] = k, x_{k+1}[0] = k +1, and |τ_{k}^{j}(k)| = j +1 < j +2 = |τ_{k+1}^{j+1}(k +1)| for 0 ≤ j ≤ k, the inequalities (7.2) and (7.3) hold for n = 1, 0 ≤ j ≤ k.

Let m ≥ 2 and assume that (7.2) and (7.3) hold for all 1 ≤ n < m, 0 ≤ j ≤ k.

We first prove (7.2) at m, i.e., L_{k}(m) ≥ L_{k+1}(m), or equivalently F_{k}^{k−1}(m) ≥ F_{k+1}^{k}(m); see Proposition 4.2. Let us abbreviate F_{k}^{k−1}(m) as c and F_{k+1}^{k}(m) as c′ and prove c′ ≤ c i.e., c′ − 1 < c. By Proposition 2.3, L_{k+1}^{k} is strictly increasing, and hence it is sufficient to prove L_{k+1}^{k}(c′ − 1) < L_{k+1}^{k}(c). Indeed, we have

L_{k+1}^{k}(c′ − 1) < m ≤ L_{k}^{k−1}(c) ≤ L_{k+1}^{k}(c),  (7.4)

where the left and middle inequalities come from Theorem 3.1. To obtain the right inequality in (7.4), we distinguish between the cases k = 1 and k ≥ 2. When k = 1, then c = m and hence L_{k}^{k−1}(c) = m < L_{2}(m) = L_{k+1}^{k}(c) by Proposition 2.3 (f). When k ≥ 2, we can use (7.3) for n = c, j = k − 1 because in this case 1 ≤ c < m by Proposition 2.1.

Now let 0 ≤ h ≤ k and let us prove (7.3) for n = m and j = h. Thanks to Equation (7.1), the case j = k is implied by the case j = k − 1, so now we can freely assume h < k. If x_{k+1}[m − 1] = k + 1, then (7.3) holds for n = m because it holds for n = m − 1 and |τ_{k}^{h}(i)| ≤ |τ_{k}^{h}(k)| < |τ_{k+1}^{h+1}(k + 1)| for all 1 ≤ i ≤ k. If x_{k+1}[m − 1] ≠ k + 1, then x_{k+1}[0:m) = τ_{k+1}(x_{k+1}[0:ℓ)) for some ℓ ≥ 1. Proposition 2.3 indicates that ℓ < L_{k+1}(ℓ) = m. Hence (7.2) holds for n = ℓ, and thus

m = L_{k+1}(ℓ) ≤ L_{k}(ℓ).

We apply L_{k}^{h} (which is monotonic by Proposition 2.3) on this inequality, and then (7.3) for n = ℓ and j = h + 1, to obtain

L_{k}^{h}(m) ≤ L_{k}^{h}(L_{k}(ℓ)) = L_{k}^{h+1}(ℓ) < L_{k+1}^{h+2}(ℓ) = L_{k+1}^{h+1}(L_{k+1}(ℓ)) = L_{k+1}^{h+1}(m).

Therefore, (7.3) holds for n = m, 0 ≤ j ≤ k. By induction, (7.2) and (7.3) hold for all n ≥ 1, 0 ≤ j ≤ k.

Corollary 7.3. For all k ≥ 1 and j ≥ 0, we have L_{k}^{j} ≥ L_{k+1}^{j}.

Proof. We proceed by induction on j. The case j = 0 is obvious. The case j = 1 is given by Equation (7.2), trivially extended to n = 0. Now assume L_{k}^{j} ≥ L_{k+1}^{j} for some j ≥ 0. For n ≥ 0, we hence have

L_{k}^{j+1}(n) = L_{k}^{j}(L_{k}(n)) ≥ L_{k+1}^{j}(L_{k}(n)) ≥ L_{k+1}^{j}(L_{k+1}(n)) = L_{k+1}^{j+2}(n),

thanks to the induction hypothesis for j and then the monotonicity of L_{k+1}^{j}, combined with the statement for j = 1. We can hence conclude by induction.

At last, we obtain the following monotonicity of the function sequence (F_{k}) over the parameter k, where the special case j = 1 is our main result Theorem 1.1.

Theorem 7.4. For all j ≥ 0, k ≥ 1, we have F_{k}^{j} ≤ F_{k+1}^{j}.

Proof. Consequence of Corollary 7.3 and Proposition 7.1.

Comparing F_{k}^{j} with F_{k+1}^{j+1} instead of F_{k+1}^{j}, we obtain the opposite inequality.

Theorem 7.5. For all k ≥ 1 and 0 ≤ j ≤ k, we have F_{k}^{j} ≥ F_{k+1}^{j+1}.

Proof. Let k ≥ 1 and 0 ≤ j ≤ k. By Proposition 7.1, the statement to prove is equivalent to L_{k+1}^{j+1} ≤ L_{k}^{j}, which is a direct consequence of Equation (7.3) and of L_{k+1}^{j+1}(0) = 0 = L_{k}^{j}(0).

To sum up, the functions (F_{k}^{j}, ≤) with their pointwise ordering form (at least) a nice lattice generated by the following basic cells for 1 ≤ j ≤ k:

\begin{aligned}F_{k−1}^{j−1} & F_{k}^{j−1} \\ & F_{k}^{j} & F_{k+1}^{j} \end{aligned} ≤ ≥ ≥ ≤ ≥

In such a cell, the vertical edge F_{k}^{j} ≤ F_{k}^{j−1} is obvious for sub-linear functions such as F_{k}. Moreover it is also a double consequence of F_{k}^{j} ≤ F_{k−1}^{j−1} ≤ F_{k}^{j−1} and F_{k}^{j} ≤ F_{k+1}^{j} ≤ F_{k}^{j−1}. Also note that the remaining unrelated functions F_{k−1}^{j−1} and F_{k+1}^{j} may actually be incomparable. For instance F_{3}^{3}(5) = 2 > 1 = F_{5}^{4}(5), while F_{3}^{3}(9) = 3 < 4 = F_{5}^{4}(5). Even if we only retain the infinitary behavior (as in Section 6), the ordering of these functions may vary. The currently known situation is presented in Figure 7.1, where the edges such as G ⟶ H mean G ≤ H. The row j = 0 of identity functions has been omitted here, id being trivially above all other F_{k}^{j}. The numbers displayed in blue alongside the nodes F_{k}^{j} are approximations of their average slopes lim \frac{1}{n}F_{k}^{j}(n) = α_{k}^{j}. If one of the functions is pointwise below another, their average slopes are ordered accordingly.^{7} Also note that the diagonal j = k and first

k = 1  k = 2  k = 3  k = 4  k = 5

j = 1  F_{1} = ⌈\frac{n}{2}⌉  F_{2} = G  F_{3} = H  F_{4}  F_{5}

j = 2  F_{1}^{2} = ⌈\frac{n}{4}⌉  F_{2}^{2} = G^{2}  F_{3}^{2} = H^{2}  F_{4}^{2}  F_{5}^{2}

j = 3  F_{1}^{3} = ⌈\frac{n}{8}⌉  F_{2}^{3} = G^{3}  F_{3}^{3} = H^{3}  F_{4}^{3}  F_{5}^{3}

j = 4  F_{1}^{4} = ⌈\frac{n}{16}⌉  F_{2}^{4} = G^{4}  F_{3}^{4} = H^{4}  F_{4}^{4}  F_{5}^{4}

j = 5  F_{1}^{5} = ⌈\frac{n}{32}⌉  F_{2}^{5} = G^{5}  F_{3}^{5} = H^{5}  F_{4}^{5}  F_{5}^{5}

0.5 0.618 0.682 0.724 0.754 0.25 0.381 0.465 0.524 0.569 0.125 0.236 ? 0.317 0.380 0.430 0.062 0.145 0.216 ? 0.275 0.324 0.031 0.090 0.147 0.199 ? 0.245

Figure 7.1: The known (F_{k}^{j}, ≤) lattice, displayed here for 1 ≤ j, k ≤ 5.

row j = 1 (in red in the figure) form an interesting chain of inequalities, with slopes ranging symmetrically between 0 and 1 (since 1 − α_{k}^{k} = α_{k}).

In Figure 7.1, some dotted edges with question marks indicate conjectured inequalities. Indeed, we conjecture that F_{k}^{k+1} ≥ F_{k+1}^{k+2} for all k ≥ 1, i.e., that Theorem 7.5 may be extended to the case j = k + 1. Actually, Corollary 6.4 already proved that F_{k}^{k+1}(n) > F_{k+1}^{k+2}(n) for sufficiently large n. Thanks to Proposition 7.1, this conjecture can also be equivalently formulated as L_{k+1}^{k+2} ≥ L_{k}^{k+1}. Said otherwise, the inequality (7.3) appears to still hold as a non-strict inequality in the case j = k + 1. Note in this case that we may indeed reach equality: we can prove L_{k}^{k+1}(k + 1) = L_{k+1}^{k+2}(k + 1).

After that, for j ≥ k+2, we prove below that F_{k}^{j} ≱ F_{k+1}^{j+1}. More precisely, when j ≥ k+2, two behaviors seem possible: either k + 2 ≤ j ≤ 2k, and we prove below that F_{k}^{j} and F_{k+1}^{j+1} are incomparable in this case; or j > 2k, in which case we conjecture that F_{k}^{j} ≤ F_{k+1}^{j+1}. For studying these questions, we now focus on L_{k+1}^{j+1}(1) − L_{k}^{j}(1).

Lemma 7.6. For all k ≥ 1, we have

L_{k+1}^{j+1}(1) − L_{k}^{j}(1) = \begin{cases}1, & if 0 ≤ j ≤ 2k; \\ −\frac{(j−2k−1)(j−2k+2)}{2}, & if 2k ≤ j ≤ 3k. \end{cases}

In particular L_{k+1}^{2k+2}(1) = L_{k}^{2k+1}(1). Moreover for all j ≥ 2k + 2, we have L_{k+1}^{j+1}(1) < L_{k}^{j}(1).

7Conversely, strictly ordered average slopes only give clues about infinitary behavior, the functions may well be pointwise incomparable due to early values.

Proof. From Proposition 2.3, we have

L_{k}^{j}(1) = \begin{cases}j + 1, & if 0 ≤ j ≤ k; \\ L_{k}^{j−1}(1) + L_{k}^{j−k}(1), & if j ≥ k. \end{cases}

For 0 ≤ j ≤ k, we have L_{k+1}^{j}(1) = j + 1 = L_{k}^{j}(1) and L_{k+1}^{j+1}(1) = j + 2 = L_{k}^{j}(1) + 1. For k < j ≤ 2k, we have

\begin{aligned}L_{k+1}^{j+1}(1) − L_{k}^{j}(1) & = L_{k+1}^{j}(1) − L_{k}^{j−1}(1) = 1, \\ L_{k+1}^{j}(1) − L_{k}^{j}(1) & = L_{k+1}^{j−1}(1) − L_{k}^{j−1}(1) − 1 = k − j, \end{aligned}

by induction on j. Note that −\frac{(j−2k−1)(j−2k+2)}{2} = 1 for j = 2k. For 2k < j ≤ 3k, we have thus

L_{k+1}^{j+1}(1) − L_{k}^{j}(1) = −\frac{(j − 2k − 2)(j − 2k + 1)}{2} + 2k − j = −\frac{(j − 2k − 1)(j − 2k + 2)}{2},

by induction on j.

Still for k ≥ 1, we now prove by induction on j that L_{k+1}^{j+1}(1) < L_{k}^{j}(1) for all j ≥ 2k + 2. This is true for j = 2k + 2: indeed, either k = 1 and we directly compute L_{2}^{5}(1) = 13 < 16 = L_{1}^{4}(1), or k ≥ 2 and hence 2k+2 = j ≤ 3k so L_{k+1}^{j+1}(1)−L_{k}^{j}(1) is given by the previous formula, which is strictly negative here. Now, for the step case of the induction, let j > 2k + 2. Then

L_{k+1}^{j+1}(1) − L_{k}^{j}(1) = (L_{k+1}^{j}(1) − L_{k}^{j−1}(1)) + (L_{k+1}^{j−k}(1) − L_{k}^{j−k}(1)).

The induction hypothesis on j − 1 indicates that the central difference above is strictly negative, while the rightmost difference is nonpositive thanks to Corollary 7.3, allowing us to conclude this induction.

Lemma 7.7. Let k ≥ 1. If j ≥ k + 2, the following value n_{j} satisfies L_{k}^{j}(n_{j}) > L_{k+1}^{j+1}(n_{j}):

n_{j} = \begin{cases}2k + 3 − j, & if k + 2 ≤ j ≤ 2k + 2; \\ 1, & if 2k + 2 ≤ j. \end{cases}

Proof. The case j ≥ 2k + 2 where n_{j} = 1 is a direct use of Lemma 7.6. Now suppose k + 2 ≤ j ≤ 2k + 2. By Proposition 2.3, we know that L_{k}^{p}(1) = p + 1 for all 0 ≤ p ≤ k. By considering p = n_{j} − 1, we obtain n_{j} = L_{k}^{n_{j}−1}(1) and hence

L_{k}^{j}(n_{j}) = L_{k}^{j}(L_{k}^{n_{j}−1}(1)) = L_{k}^{j+n_{j}−1}(1) = L_{k}^{2k+2}(1).

Similarly, n_{j} = L_{k+1}^{n_{j}−1}(1) and L_{k+1}^{j+1}(n_{j}) = L_{k+1}^{2k+3}(1), which is strictly less than L_{k}^{2k+2}(1) by Lemma 7.6.

In particular, this last lemma implies that L_{k}^{j} ≰ L_{k+1}^{j+1} when j ≥ k + 2, with n_{j} as counterexample. Thanks to Proposition 7.1, this means equivalently that F_{k}^{j} ≱ F_{k+1}^{j+1} when j ≥ k + 2, with n = L_{k}^{j}(n_{j}) as counterexample. Moreover, when k + 2 ≤ j ≤ 2k, Lemma 7.6 implies that L_{k}^{j} ≱ L_{k+1}^{j+1}, with n = 1 as counterexample, and hence that L_{k}^{j} and L_{k+1}^{j+1} are incomparable, and equivalently that F_{k}^{j} and F_{k+1}^{j+1} are also incomparable.

We conclude this section with a last conjecture about F_{k}, as always for k ≥ 1. From Corollary 6.4, we know that the inequality F_{k}(n) ≤ F_{k+1}(n) becomes strict when n is large enough. Actually, we conjecture an explicit bound N_{k} = \frac{1}{2}(k + 1)(k + 6), for which F_{k}(n) < F_{k+1}(n) as soon as n > N_{k}. At least, it can be proved that F_{k}(N_{k}) = F_{k+1}(N_{k}), so the bound cannot be less than N_{k}, but it remains to be confirmed that no equality occurs after N_{k}. These constants N_{k} can also be expressed as \frac{1}{2}(k + 3)(k + 4) − 3 and satisfy N_{k+1} = N_{k} + (k + 4). In particular N_{1} = 7 and N_{2} = 12 and N_{3} = 18. Interestingly, we also have L_{k+1}(N_{k}) = L_{k+2}(N_{k}). Finally, this conjecture implies two other interesting statements:

• F_{k}(n) < F_{k+1}(n + 1) for all n ≥ 2;

• L_{k+1}(n) > L_{k+2}(n) for all n > N_{k}.

8 More letter counting

Several results and conjectures of the previous section can be rephrased into statements about the number of occurrences of certain letters in words x_{k}. In particular, let us consider again the letter 1 and study C_{k}^{(=1)}.

Proposition 8.1. For all k ≥ 1 and n ≥ 0, we have C_{k}^{(=1)}(n) ≥ C_{k+1}^{(=1)}(n).

Proof. When k ≥ 2, this is a consequence of Proposition 4.3 and Theorem 1.1. For k = 1, we have C_{1}^{(=1)}(n) = n ≥ C_{2}^{(=1)}(n).

Considering the letter 2, we conjecture that C_{k}^{(=2)}(n) ≥ C_{k+1}^{(=2)}(n) for all k ≥ 3, n ≥ 0. In particular, this is a consequence of the conjecture F_{k}^{k+1} ≥ F_{k+1}^{k+2} mentioned in the previous section: when combining it with Equation (4.3), we get

C_{k}^{(=2)}(n) ≥ C_{k+1}^{(=2)}(n) for all k > 2 and n ≥ 2;

we can then relax the condition on n because all these quantities are zero when n is 0 or 1. (In the latter case, x_{k}[0] = k ≠ 2 and similarly for x_{k+1}.)

Actually, the property C_{k}^{(=2)} ≥ C_{k+1}^{(=2)} also extends to k = 2, and is easy to prove in this case, since for all n ≥ 0, we have C_{2}^{(=2)}(n) ≥ C_{3}^{(=3)}(n) (by Equation 7.2, trivially extended to n = 0) as well as C_{3}^{(=3)}(n) ≥ C_{3}^{(=2)}(n); indeed, in x_{3}, any occurrence of the letter 2 is in a subword 312. We cannot extend further: for k = 1, there is no letter 2 in the word x_{1}, hence C_{1}^{(=2)}(n) = 0 while C_{2}^{(=2)}(n) = F_{2}(n) by Equation 4.1, which differs from 0 as soon as n ≥ 1.

For the letters 3 ≤ i < k, there is no pointwise monotonicity between C_{k}^{(=i)} and C_{k+1}^{(=i)}:

Proposition 8.2. For 3 ≤ i < k, we have

• C_{k}^{(=i)}(n) < C_{k+1}^{(=i)}(n) when n = i + L_{k}^{2k+2}(1),

• C_{k}^{(=i)}(n) > C_{k+1}^{(=i)}(n) when n = i + L_{k+1}^{k+i}(1).

Proof. After Lemma 7.7, we noticed that F_{k}^{j} and F_{k+1}^{j+1} are incomparable for all j ≥ k + 2. Some counterexamples are L_{k}^{j}(n_{j}) in one direction and L_{k+1}^{j+1}(1) in the other (by Proposition 7.1). Now we use Equation (4.3) to express this in terms of the number of occurrences of letters, by choosing j = k + i − 1. When 3 ≤ i < k, we indeed have j ≥ k + 2 (and also j ≤ 2k + 2). Due to the shape of Equation (4.3), the previous counterexamples are now shifted by i. Moreover, here

n_{j} = 2k + 3 − j = k + 4 − i = L_{k}^{k+3−i}(1),

and hence

L_{k}^{j}(n_{j}) = L_{k}^{k+i−1}(L_{k}^{k+3−i}(1)) = L_{k}^{2k+2}(1).

For instance, for k = 5 and i = 4, we have C_{5}^{(=4)}(49) = 5 < 6 = C_{6}^{(=4)}(49) while C_{5}^{(=4)}(20) = 2 > 1 = C_{6}^{(=4)}(20).

Finally, we compare these quantities for sufficiently large n. Let k ≥ 1 and 1 ≤ i < k. By Corollary 6.4 and Equation (4.3), we obtain that C_{k}^{(=i)} >_{∞} C_{k+1}^{(=i)} at least when α_{k} ≥ 1 − \frac{1}{i}, which in particular happens when (i − 1)^{2} ≤ k. Note that this condition is always satisfied when i = 1 or i = 2. Otherwise, for i ≥ 3, small values of k may exhibit the opposite infinitary behavior. For example C_{6}^{(=5)} <_{∞} C_{7}^{(=5)} since

lim_{n→∞} \frac{1}{n}C_{6}^{(=5)}(n) = α_{6}^{10} ≈ 0.0813, lim_{n→∞} \frac{1}{n}C_{7}^{(=5)}(n) = α_{7}^{11} ≈ 0.0819.

9 Acknowledgments

The authors are deeply grateful to Yining Hu, who made this joint work possible. We also thank the anonymous referees for their helpful remarks.

The third author was supported by the ERC grant DynAMiCs (101167561) of the European Research Council, the bilateral grant SYMDYNAR (ANR-23-CE40-0024 and FWF I 6750) of the Agence Nationale de la Recherche and the Austrian Science Fund, and by the ANR project IZES (ANR-22-CE40-0011).

References

[1] J.-P. Allouche, J. Cassaigne, J. Shallit, and L. Q. Zamboni, A taxonomy of morphic sequences, 2017. Arxiv preprint arXiv:1711.10807 [cs.FL], November 29 2017. Available at arXiv:1711.10807.

[2] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.

[3] M. Dekking, On Hofstadter’s G-Sequence, J. Integer Sequences 26 (2023), Article 23.9.2.

[4] K. Dilcher, On a class of iterative recurrence relations, In G. E. Bergum, A. N. Philippou, and A. F. Horadam, editors, Applications of Fibonacci Numbers, Vol. 5, pp. 143–158. Springer, 1993.

[5] P. J. Downey and R. E. Griswold, On a family of nested recursions, Fibonacci Quart. 22 (1984), 310–317.

[6] L. Ericksen and P. G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, Fibonacci Quart. 50 (2012), 11–18.

[7] M. Erné, J. Koslowski, A. Melton, and G. E. Strecker, A primer on Galois connections, Ann. N. Y. Acad. Sci. 704 (1993), 103–125.

[8] N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, Vol. 1794 of Lecture Notes in Mathematics, Springer, 2002. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel.

[9] C. Frougny, Z. Masáková, and E. Pelantová, Complexity of infinite words associated with beta-expansions, RAIRO Theor. Informatics Appl. 38 (2004), 163–185. Corrigendum, 38 (2004), 269–271.

[10] D. Gault and M. Clint, “Curiouser and curiouser” said Alice. Further reflections on an interesting recursive function, Int. J. Comput. Math. 26 (1988), 35–43.

[11] L. Goldberg and A. S. Fraenkel, Patterns in the generalized Fibonacci word, applied to games, Discrete Math. 341 (2018), 1675–1687.

[12] K. Hare and J. C. Saunders, Generalised Fibonacci sequences constructed from balanced words, J. Number Theory 231 (2022), 349–377.

[13] D. R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, 1979.

[14] C. Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quart. 33 (1995), 3–8.

[15] P. Letouzey, Coq/Rocq proofs about Hofstadter’s function G. 2015–2025. https://

github.com/letouzey/hofstadter_g.

[16] P. Letouzey, Hofstadter’s problem for curious readers, 2015. Research Report, Université Paris Diderot and INRIA Paris. hal-01195587v4.

[17] D. S. Meek and G. H. J. Van Rees, The solution of an iterated recurrence, Fibonacci Quart. 22 (1984), 101–104.

[18] J. L. Ramírez, G. N. Rubiano, and R. De Castro, A generalization of the Fibonacci word fractal and the Fibonacci snowflake, Theoret. Comput. Sci. 528 (2014), 40–56.

[19] The Rocq Core Team, The Rocq proof assistant. 2025–2026 (and 1985–2025 under the

    name Coq). https://rocq-prover.org.

[20] E. Selmer, On the irreducibility of certain trinomials, Math. Scand. 4 (1956), 287–302.

[21] J. Shallit, Proving properties of some greedily-defined integer recurrences via automata theory, Theoret. Comput. Sci. 988 (2024), 114363.

[22] N. J. A. Sloane and The OEIS Foundation Inc., The on-line encyclopedia of integer sequences, 2026. Published electronically at https://oeis.org.

[23] B. Tan and Z.-Y. Wen, Some properties of the Tribonacci sequence, European J. Combin. 28 (2007), 1703–1719.

2020 Mathematics Subject Classification: Primary 11B37; Secondary 11B39, 68R15, 68V15. Keywords: Hofstadter sequence, Fibonacci word, theorem prover, proof assistant, Rocq.

(Concerned with sequences \underline{A005206}, \underline{A005374}, \underline{A005375}, \underline{A005376}, and \underline{A100721}.)

Received September 27 2024; revised versions received April 17 2026; May 15 2026. Published in Journal of Integer Sequences, May 19 2026.

Return to Journal of Integer Sequences home page.