On Functions Expressible as Words on a Pair of Beatty Sequences

Christian Ballot Département de Mathématiques et Informatique Université de Caen-Normandie France

                  christian.ballot@unicaen.fr

Abstract Let a(n) = ⌊nα⌋ and b(n) = ⌊nα^{2}⌋, where α = \frac{1+\sqrt{5}}{2}. Then a theorem of Carlitz et al. states that each function f, composed of several a’s and b’s, can be expressed in the form c_{1}a + c_{2}b − c_{3}, where c_{1} and c_{2} are consecutive Fibonacci numbers determined by the numbers of a’s and of b’s composing f and c_{3} is a nonnegative constant. We provide generalizations of this theorem to two infinite families of complementary pairs of Beatty sequences. The particular case involving ‘Narayana’ numbers is examined in depth. The details reveal that x_{n} = ⌊α^{3}⌊α^{3}⌊⋯ ⌊α^{3}⌋ ⋯⌋⌋⌋, with n nested pairs of ⌊ ⌋, is a 7th-order linear recurrence, where α is the dominant zero of x^{3} − x^{2} − 1.

1 Introduction

If α is a positive irrational number, then a(n) = ⌊nα⌋ is said to be a Beatty sequence. A pair of Beatty sequences a(n) = ⌊nα⌋ and b(n) = ⌊nβ⌋ is said to be complementary whenever their ranges form a partition of the positive integers. A famous theorem states that complementarity occurs if and only if 1/α + 1/β = 1. According to Kimberling [10], though this theorem was stated as a problem [3], it had appeared even earlier in the book [15, p. 123].

The lower and upper Wythoff sequences, i.e., the sequences a(n) = ⌊nα⌋ and b(n) = ⌊nα^{2}⌋, where α = \frac{1+\sqrt{5}}{2}, are a pair of complementary Beatty sequences. This pair has often been considered, in part because the positions (a(n), b(n)) are winning positions in a variant of the game of Nim [22]. Carlitz et al. [6] and later again Kimberling [9] studied the functions (w(n))_{n≥1}, where w = ℓ_{1} ∘ ℓ_{2} ∘ ⋯ ∘ ℓ_{s} and each ℓ_{i} is either the a or the b sequence. The following lemma was proved

Lemma 1. Let a(n) = ⌊nα⌋ and b(n) = ⌊nα^{2}⌋, where α = (1 + \sqrt{5})/2. Then

a^{2} = b − 1,
ba = a + b − 1,
ab = a + b,
b^{2} = a + 2b,

where ℓ_{1}ℓ_{2} stands for ℓ_{1} ∘ ℓ_{2} and ℓ^{2} for ℓℓ.

One of the key facts is that, as α^{2} = α + 1, we have b(n) = a(n) + n, for all integers n. Here is essentially Theorem 13 of Carlitz et al. [6] and the principal theorem of Kimberling [9], proved in both instances by induction on s using Lemma 1.

Theorem 2. Let w = ℓ_{1} ∘ ℓ_{2} ∘ ⋯ ∘ ℓ_{s}, (s ≥ 1), where each ℓ_{i} is either a or b. Assume x and y are, respectively, the number of a’s and the number of b’s in w. Then,

w(n) = F_{x+2y−2} a(n) + F_{x+2y−1} b(n) − e_{w},

where e_{w} = F_{x+2y+1} − w(1) ≥ 0 and F_{k} denotes the kth Fibonacci number.

As usual, the Fibonacci sequence (F_{k}) is defined by F_{0} = 0, F_{1} = 1 and F_{k+2} = F_{k+1} +F_{k} for all integers k. With f^{x} denoting the x-fold composite function f ∘ f ∘ ⋯ ∘ f, we state a corollary from material observed by Kimberling [9].

Corollary 3. We have a^{x} = F_{x−2}a+F_{x−1}b−F_{x+1}+1 and b^{y} = F_{2y−2}a+F_{2y−1}b. In particular, b^{y}(1) = F_{2y+1}.

For each pair a(n) = ⌊nα⌋ and b(n) = ⌊nβ⌋ of complementary Beatty sequences, we will always take α to be less than β. Then we necessarily have 1 < α < 2 < β = α/(α − 1).

This paper studies two infinite families of pairs of complementary Beatty sequences. Each of the two families contains the Wythoff pair as its simplest case. For each family, our main goal is to find a sensible generalization of Theorem 2.

Our investigation begins in Section 2 by looking at the pair of complementary Beatty sequences (α, β) = (\sqrt{2}, 2 + \sqrt{2}). That is, a(n) = ⌊n\sqrt{2}⌋ and b(n) = ⌊n(2 + \sqrt{2})⌋. This pair satisfies the obvious property b(n) = a(n) + 2n instead of b(n) = a(n) + n for the Wythoff pair. In Section 3, we study the general pair of complementary Beatty sequences where b(n) = a(n) + rn, r ≥ 1 any integer. We obtain Theorem 8, a most general theorem.

The second infinite family we study stems from the observation [2] that for all integers q ≥ 2, the complex polynomial x^{q} − x^{q−1} − 1 has a simple dominant real zero α, 1 < α < 2, and the pair (α, β), where β = α^{q}, generates a complementary pair of Beatty sequences (a(n), b(n)). Section 4 studies in detail the case q = 3. Then, of course, β is the cube rather than the square of α, as was the case for the Wythoff pair. Section 5 is a brief section on the case q = 4. A sixth section deals with the general case q ≥ 2, where we reach our most general result, Theorem 32. We believe beginning with particular cases makes the transition to the general case both more readable and more enjoyable. However, readers can skip Sections 2 and 5, if they wish. Yet in Sections 2, 4, and 5, we investigate the functions e_{w} in more detail than in the general cases. For instance, the functions e_{w} studied in Sections 2 and 4 are nonnegative, in contrast to their general counterparts in Theorems 8 and 32.

A subsidiary investigation of the paper is the study of the sequences (b^{y}(n))_{y}. This function turns out to be a second-order linear recurrence whose characteristic polynomial is the minimal polynomial of β not just in the Wythoff case, but in all (a(n), a(n) + rn) cases for r ≥ 1, as shown in the later part of Section 3. Also, Section 4, where a(n) = ⌊αn⌋ and b(n) = ⌊α^{3}n⌋, α^{3} = α^{2} + 1, α > 1, is divided into two subsections, the second of which studies the behavior of b^{y}(1) = ⌊α^{3}⌊α^{3}⌊⋯ ⌊α^{3}⌋ ⋯⌋⌋⌋, with y nested pairs ⌊ ⌋. This sequence (b^{y}(1))_{y} turns out to be a seventh-order linear recurrence. We find several explicit formulas for it. Note that the corresponding sequence (a^{x}(1))_{x} is the constant sequence equal to 1 as ⌊α⌋ = 1 for all complementary Beatty pairs.

We now relate our paper to general questions and other work. We begin with the mention that Stolarsky [20] compiled an extended bibliography of work linked to Beatty sequences done before 1973. A quite general question is ‘what sort of behavior and structures emerge from all possible compositions of a given set of functions?’ For a single function this is the problem of analyzing iteration (e.g., see the comments on b^{y}(n) above). Here we examine functions of the form

g(n) = ⌊nα_{i}⌋

(i.e., Beatty sequences), where the α_{i} are algebraic irrationalities. In various cases of interest we determine the nature of ‘homogeneous’ compositions

g_{1}(g_{2}(⋯ (g_{k}(n)) ⋯).

There has also been some study of ‘inhomogeneous’ compositions such as

g_{1}(g_{2}(n) + c_{1}n + c_{2})

in the Beatty context. See [13], especially formula (1.1.4), and [7], in particular Theorem 1 of §2. Boshernitzan and Fraenkel [5] discussed characteristic properties of functions of the form

g(n) = ⌊nα_{i} + β_{i}⌋,

but perhaps the study of arbitrarily long compositions of such functions has not been done in any detail. Fraenkel et al. [8] studied more general combinations of such functions. Cases in which the most interesting results are found frequently involve numbers α that are real algebraic integers larger than their conjugates. Even more special are cases in which α is a Pisot number. For example, the dominant real zero of x^{q}−x^{q−1}−1 is a Pisot number for q = 2, 3, and 4. In §4, i.e., in Section 4, we examine in special detail the ‘Narayana case’ q = 3. Bertin et al. [4] published a general reference book on Pisot numbers and their relatives. In fact, the Fibonacci (q = 2) and Narayana cases involve a dominant zero that comes from the finite set of ‘special Pisot numbers’. The significance of these numbers appears in various papers [11, 12, 17]. Smyth [19] provided a definitive complete determination of them. The α of §5 is also a special Pisot number. In connection with §6 we note that the dominant zero of P (q, x) = x^{q} − x^{q−1} − 1 is not Pisot for q ≥ 6, and that P (5, x) = (x^{3} − x − 1)(x^{2} − x + 1). It has been noted that a full understanding of the Beatty sequences and Wythoff pairs related to \sqrt{5} involves recurrences of degree 4. This is the basic theme of two papers [21, 16]. Here in §4 we find that the study of Beatty sequences corresponding to the ‘Narayana’ cubic irrationality (one of the special Pisot numbers) inevitably involves recurrences of degree 7. See Problems 36 and 37 of Section 7 for precise questions.

Indeed, Section 7, our final section, proposes five problems for further consideration.

By convention, throughout the paper, the sums ∑_{i≤j≤k} a_{j} or ∑_{j=i}^{k} a_{j} are zero whenever k < i. If α is an irrational real number, then the uniform distribution of the sequence of fractional parts of the multiples of α, i.e., the sequence ({nα})_{n≥1}, is a well-known fact that we occasionally use.

2 The (\sqrt{2}, 2 + \sqrt{2}) case

Thus, we now have a(n) := ⌊nα⌋ and b(n) := ⌊nβ⌋, where α = \sqrt{2} and β = 2 + \sqrt{2}.

Lemma 4. For all integers n ≥ 1, we have

a^{2}(n) = −a(n) + b(n) − d(n),
ba(n) = a(n) + b(n) − d(n),
ab(n) = a(n) + b(n),
b^{2}(n) = a(n) + 3b(n),

where d(n) is the function ⌈\sqrt{2}\{n\sqrt{2}\}⌉ which is either 1 or 2.

Proof. See the proof of the more general Lemma 6 of the next section.

Theorem 5. Let w = ℓ_{1} ∘ ℓ_{2} ∘ ⋯ ∘ ℓ_{s}, (s ≥ 1), where each ℓ_{i} is either a or b. If w has an even number of a’s, say 2x, and y b’s (x ≥ 0, y ≥ 0), then

w(n) = 2^{x}u_{y} a(n) + 2^{x}v_{y} b(n) − e(n),  (1)

whereas, if w has 2x + 1 a’s and y b’s, then

w(n) = 2^{x+1}v_{y−1} a(n) + 2^{x}u_{y+1} b(n) − e(n),  (2)

where in both cases e = e_{w} is some nonnegative integral bounded function of n that depends on w, and (u_{y}) and (v_{y}) are the recurrences with characteristic polynomial x^{2} − 4x + 2 that satisfy u_{1} = 0, u_{2} = 1 and v_{1} = 1, v_{2} = 3.

Proof. It is easy to verify that

\begin{aligned}u_{y} + v_{y} & = u_{y+1} & v_{y} − u_{y} & = 2v_{y−1} \\ u_{y} + 3v_{y} & = v_{y+1} & u_{y+1} − 2v_{y−1} & = 2u_{y}. \end{aligned}  (3)

We may proceed by induction on s. Both (1) and (2) trivially hold for s = 1 with e = 0, as v_{−1} = v_{0} = 1/2. Assuming the property holds for some s ≥ 1 and w is a ‘word’ with s letters, we check the property for wa and wb. There are four cases to treat as the form of w depends on the parity of the number of a’s in w. If w has 2x a’s and y b’s, then, by the inductive hypothesis,

wa(n) = w(a(n)) = 2^{x}u_{y} a^{2}(n) + 2^{x}v_{y} b(a(n)) − e(a(n)),

for some nonnegative bounded function e. Using Lemma 4 and gathering together the coefficients of a(n) and b(n), we find that

wa(n) = 2^{x}(v_{y} − u_{y}) a(n) + 2^{x}(u_{y} + v_{y}) b(n) − e′(n),

with e′(n) = u_{y+1}d(n) + e(a(n)). By (3), wa(n) = 2^{x+1}v_{y−1} a(n) + 2^{x}u_{y+1} b(n) − e′(n), which is the expected result for the word wa. We proceed in the same manner for wb(n) and obtain

wb(n) = 2^{x}(u_{y} + v_{y}) a(n) + 2^{x}(u_{y} + 3v_{y}) b(n) − e(b(n)).

We conclude using the first pair of equations of (3). If w has 2x + 1 a’s and y b’s, then the inductive hypothesis yields

wa(n) = 2^{x+1}v_{y−1} a^{2}(n) + 2^{x}u_{y+1} ba(n) − e(a(n)).

Using Lemma 4, we find that wa(n) = 2^{x}(u_{y+1} − 2v_{y−1}) a(n) + 2^{x}(u_{y+1} + 2v_{y−1}) b(n) − e′′(n), where e′′(n) = 2^{x}(2v_{y−1} + u_{y+1})d(n) + e(a(n)). Since v_{−1} = v_{0} = 1/2, we see that e′′ is nonnegative in all cases. We conclude using the second pair of identities of (3), as u_{y+1} − 2v_{y−1} = 2u_{y} and u_{y+1} + 2v_{y−1} = (u_{y+1} − 2v_{y−1}) + 4v_{y−1} = 2(u_{y} + 2v_{y−1}) = 2v_{y}. Finally, we obtain, in similar fashion, wb(n) = 2^{x}(u_{y+1} + 2v_{y−1}) a(n) + 2^{x}(3u_{y+1} + 2v_{y−1}) b(n) − e(b(n)). We just saw that u_{y+1} + 2v_{y−1} = 2v_{y}. Moreover,

3u_{y+1} + 2v_{y−1} = 2u_{y+1} + 2v_{y} = u_{y+1} + (u_{y+1} + 2v_{y}) = u_{y+1} + v_{y+1} = u_{y+2},

according to the two identities on the first line of (3).

3 The general (α, α + r) case, (r ≥ 1)

We fix an integer r ≥ 1. If β = α + r, then we see that b(n) = a(n) + rn. Solving 1/α + 1/(α + r) = 1 leads to α^{2} + (r − 2)α − r = 0. Since α ∈ (1, 2), we find that α = 1 + \frac{\sqrt{r^{2}+4}−r}{2}. Thus, β = 1 + \frac{\sqrt{r^{2}+4}+r}{2} and β satisfies β^{2} − (r + 2)β + r = 0. As r^{2} + 4 is never a perfect square, we note that α and β are irrational.

Lemma 6. For all integers n ≥ 1, we have

a^{2}(n) = (1 − r)a(n) + b(n) − d(n),
ba(n) = a(n) + b(n) − d(n),
ab(n) = a(n) + b(n),
b^{2}(n) = a(n) + (r + 1)b(n),

where d(n) is the function ⌈(α + r − 2){nα}⌉ whose range is {1, 2, …, r}.

Proof. Using α^{2} = (2 − r)α + r and {αn} = {βn}, we find that

a^{2}(n) = ⌊α⌊αn⌋⌋ = ⌊α^{2}n − α{αn}⌋ = ⌊((1 − r)α + (α + r))n − α{αn}⌋
= (1 − r)a(n) + b(n) + ⌊(1 − r){αn} + {αn} − α{αn}⌋
= (1 − r)a(n) + b(n) − ⌈(r − 2 + α){αn}⌉.

But the sequence ({αn})_{n≥1} is dense in (0, 1) and r − 2 + α lies in (r − 1, r), so the range of d is {1, 2, …, r}. Hence, b(a(n)) = ⌊(α + r)a(n)⌋ = ra(n) + a^{2}(n) = a(n) + b(n) − d(n). Now

ab(n) = ⌊α(α + r)n − α{(α + r)n}⌋ = ⌊αn + (α + r)n − α{αn}⌋
= a(n) + b(n) + ⌊(2 − α){αn}⌋ = a(n) + b(n),

as both 2 − α and {αn} lie in the interval (0, 1). Thus,

b^{2}(n) = ⌊(α + r)b(n)⌋ = rb(n) + ab(n) = a(n) + (r + 1)b(n).

Define (U_{n}^{α})_{n≥0} and (U_{n}^{β})_{n≥0}, respectively, as the fundamental Lucas sequences associated with (x − α)(x − ᾱ) and with (x − β)(x − β̄), where ᾱ and β̄ are the respective algebraic conjugates of α and β. Thus,

U_{n}^{α} = \frac{α^{n} − ᾱ^{n}}{α − ᾱ} and U_{n}^{β} = \frac{β^{n} − β̄^{n}}{β − β̄} .  (4)

We also define two matrices

E_{a} = (\begin{matrix}1 − r & 1 \\ 1 & 1 \end{matrix}) and E_{b} = (\begin{matrix}1 & 1 \\ 1 & 1 + r \end{matrix}) .  (5)

Lemma 7. For all integers x ≥ 0 and y ≥ 0, we find that

E_{a}^{x} = (\begin{matrix}U_{x+1}^{α} − U_{x}^{α} & U_{x}^{α} \\ U_{x}^{α} & U_{x}^{α} + rU_{x−1}^{α} \end{matrix}) and E_{b}^{y} = (\begin{matrix}U_{y}^{β} − rU_{y−1}^{β} & U_{y}^{β} \\ U_{y}^{β} & U_{y+1}^{β} − U_{y}^{β} \end{matrix}) .

Proof. The characteristic polynomials of E_{a} and E_{b} are, respectively, the minimal polynomials of α and β. Thus, their respective eigenvalues are {α, ᾱ} and {β, β̄}. Thus, we may diagonalize the two matrices E_{a} and E_{b} and find that

E_{a} = P_{a} (\begin{matrix}α & 0 \\ 0 & ᾱ \end{matrix}) P_{a}^{−1} and E_{b} = P_{b} (\begin{matrix}β & 0 \\ 0 & β̄ \end{matrix}) P_{b}^{−1},

where we took

P_{a} = (\begin{matrix}α − 1 & ᾱ − 1 \\ 1 & 1 \end{matrix}) and P_{b} = (\begin{matrix}1 & 1 \\ β − 1 & β̄ − 1 \end{matrix}) ,

as eigenvector matrices. We then simply calculate

E_{a}^{x} = P_{a} (\begin{matrix}α^{x} & 0 \\ 0 & ᾱ^{x} \end{matrix}) P_{a}^{−1} and E_{b}^{y} = P_{b} (\begin{matrix}β^{y} & 0 \\ 0 & β̄^{y} \end{matrix}) P_{b}^{−1},

noting that for x = 0 or for y = 0, the expressions in the lemma produce the identity matrix

(\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}). Indeed, U_{−1}^{α} = 1/r and U_{−1}^{β} = −1/r.

Theorem 8. Let r ≥ 1 be an integer, α = 1 + \frac{\sqrt{r^{2}+4}−r}{2} and β = α + r. Define a(n) = ⌊αn⌋ and b(n) = ⌊βn⌋. Let w = ℓ_{1} ∘ ℓ_{2} ∘ ⋯ ∘ ℓ_{x+y}, where ℓ_{i} = a for x ≥ 0 values and ℓ_{i} = b for the remaining y values of i, 1 ≤ i ≤ x + y. Then for all n ≥ 1

w(n) = s_{x,y} a(n) + t_{x,y} b(n) − d_{w}(n),  (6)

where

\begin{matrix}s_{x,y} = U_{x}^{α}U_{y}^{β} − rU_{y−1}^{β}(U_{x}^{α} − U_{x−1}^{α}) = U_{x}^{α}U_{y}^{β} + U_{y−1}^{β}(U_{x+1}^{α} − 2U_{x}^{α}), \\ t_{x,y} = U_{x}^{α}U_{y}^{β} + rU_{x−1}^{α}(U_{y}^{β} − U_{y−1}^{β}) = U_{x}^{α}U_{y}^{β} + U_{x−1}^{α}(U_{y+1}^{β} − 2U_{y}^{β}), \end{matrix}  (7)

(U_{x}^{α}) and (U_{y}^{β}) were defined in (4) and d_{w} is an integral and bounded function of n that depends on w.

Proof. Suppose w(n) = s_{w}a(n) + t_{w}b(n) − d_{w}(n), where s_{w} and t_{w} are integers that do not depend on n and d_{w} is an integral and bounded function of n. Then, by Lemma 6, we find that

\begin{aligned}wa(n) & = ((1 − r)s_{w} + t_{w})a(n) + (s_{w} + t_{w})b(n) − d_{wa}(n), \\ wb(n) & = (s_{w} + t_{w})a(n) + (s_{w} + (r + 1)t_{w})b(n) − d_{wb}(n), \end{aligned}  (8)

where d_{wa}(n) = (s_{w} + t_{w})d_{a^{2}}(n) + d_{w}(a(n)) and d_{wb}(n) = d_{w}(b(n)). Thus we see from (8) that

E_{a} · (\begin{matrix}s_{w} \\ t_{w} \end{matrix}) = (\begin{matrix}s_{wa} \\ t_{wa} \end{matrix}) and E_{b} · (\begin{matrix}s_{w} \\ t_{w} \end{matrix}) = (\begin{matrix}s_{wb} \\ t_{wb} \end{matrix}) ,

where the matrices E_{a} and E_{b} were defined in (5).

An easy induction on x + y shows that for all words w with x letters a and y letters b and all n ≥ 1, 0 ≤ α^{x}β^{y}n − w(n) ≤ β^{x+y}. Indeed, if ℓ = a or b and ℓ(n) = ⌊λn⌋, then 0 ≤ α^{x}β^{y}ℓ(n) − wℓ(n) ≤ β^{x+y}, by the inductive hypothesis. But ℓ(n) = λn − {λn}, so 0 ≤ α^{x}β^{y}λn − wℓ(n) ≤ β^{x+y} + α^{x}β^{y}{λn} ≤ 2β^{x+y} ≤ β^{x+y+1}, as β > 2 > α. Therefore, using the triangle inequality, we find that |w(n) − w_{0}(n)| ≤ 2β^{x+y} for all w satisfying the hypotheses of the theorem and all n ≥ 1, where w_{0} = a^{x}b^{y}. Thus, it suffices to prove the

theorem for the function w = w_{0}. Since b = 0 · a + 1 · b, we can find the vector (\begin{matrix}s_{w} \\ t_{w} \end{matrix}) by

computing the matrix product E_{a}^{x}E_{b}^{y−1} (\begin{matrix}0 \\ 1 \end{matrix}). By Lemma 7,

E_{a}^{x}E_{b}^{y−1} (\begin{matrix}0 \\ 1 \end{matrix}) = (\begin{matrix}U_{x+1}^{α} − U_{x}^{α} & U_{x}^{α} \\ U_{x}^{α} & U_{x}^{α} + rU_{x−1}^{α} \end{matrix}) (\begin{matrix}U_{y−1}^{β} \\ U_{y}^{β} − U_{y−1}^{β} \end{matrix})

= (\begin{matrix}U_{x}^{α}U_{y}^{β} + U_{y−1}^{β}(U_{x+1}^{α} − 2U_{x}^{α}) \\ U_{x}^{α}U_{y}^{β} + rU_{x−1}^{α}(U_{y}^{β} − U_{y−1}^{β}) \end{matrix}) .

The other expressions for s_{x,y} and t_{x,y} in (7) are obtained using the relations U_{x+1}^{α} = (2 − r)U_{x}^{α} + rU_{x−1}^{α} and (2 + r)U_{y}^{β} − rU_{y−1}^{β} = U_{y+1}^{β}, respectively. Our derivation assumed y ≥ 1.

However, it is easy to check that putting y = 0 in (7) yields (\begin{matrix}s_{x,0} \\ t_{x,0} \end{matrix}) = (\begin{matrix}U_{x}^{α} − U_{x−1}^{α} \\ U_{x−1}^{α} \end{matrix}), which

equals E_{a}^{x−1} (\begin{matrix}1 \\ 0 \end{matrix}) = (\begin{matrix}s_{a^{x}} \\ t_{a^{x}} \end{matrix}), by Lemma 7.

Remark 9. The functions s_{x,y} and t_{x,y} are integral linear recurrences in x with characteristic polynomial the minimal polynomial of α when y is fixed, and linear recurrences in y with characteristic polynomial the minimal polynomial of β when x is fixed. Remark 10. One can easily recover s_{x,y} and t_{x,y} when r = 1 or r = 2 obtained in Theorems 2 and 5. For instance, if r = 1, then U_{x}^{α} = F_{x} and U_{y}^{β} = F_{2y} so s_{x,y} = F_{x}F_{2y} + F_{2y−2}(F_{x+1} − 2F_{x}) = F_{x}F_{2y} −F_{x−2}F_{2y−2}. To see that F_{x}F_{2y} −F_{x−2}F_{2y−2} = F_{x+2y−2}, it is enough to observe that both sides of the equation are linear recurrences satisfying the Fibonacci recursion once y is fixed. Thus, we are left with verifying equality, say, at x = 0 and x = 1. Remark 11. In contrast with the cases r = 1 or r = 2, the functions d_{w}(n) in (6) are not necessarily always nonnegative when r ≥ 3. For instance, for r = 3,

d_{a^{3}}(n) = ⌈(α + 1){αa(n)}⌉ − ⌈(α + 1){nα}⌉,

which is −1 for n = 6.

In the Wythoff case, as we can see from Corollary 3, the sequences (b^{y}(n))_{y} for a fixed integer n ≥ 1 are all second-order recurrences with characteristic polynomial the minimal polynomial of β = α + 1. The next two corollaries show this phenomenon holds for all pairs of Beatty sequences stemming from a pair (α, α + r), (r ≥ 1).

Corollary 12. For all y ≥ 0 and all n ≥ 1, we find that

b^{y}(n) = u_{y}a(n) + v_{y}b(n),

where (u_{y}) and (v_{y}) are both second-order linear recurrences with characteristic polynomial x^{2} − (r + 2)x + r and initial values u_{1} = 0, u_{2} = 1 and v_{1} = 1, v_{2} = r + 1.

Proof. We saw in (8) that d_{wb}(n) = d_{w}(b(n)). But for w = b, d_{w} = 0. Hence, we see inductively that d_{b^{y}} = 0, for all y ≥ 1. Therefore, by Theorem 8, we get

b^{y}(n) = U_{y−1}^{β}a(n) + (U_{y}^{β} − U_{y−1}^{β})b(n).

Both U_{y−1}^{β} and U_{y}^{β}−U_{y−1}^{β} are linear recurrences with characteristic polynomial x^{2}−(r+2)x+r, the minimal polynomial of β, and their initial conditions are those indicated. For y = 0, b^{y}(n) = n and

U_{y−1}^{β}a(n) + (U_{y}^{β} − U_{y−1}^{β})b(n) = U_{−1}^{β}(a(n) − b(n)) = −r^{−1}(−rn) = n.

Corollary 13. Given n ≥ 1, the sequence (b^{y}(n))_{y} is linear recurrent with characteristic polynomial the minimal polynomial of β, namely x^{2} − (r + 2)x + r. In particular, (b^{y}(1))_{y} = v_{y+1}, where the sequence (v_{y}) was defined in the statement of Corollary 12.

Proof. By Corollary 12, once n is fixed, b^{y}(n) is a linear combination of u_{y} and v_{y}. Moreover, b^{y}(1) = a(1)u_{y} + b(1)v_{y} = ⌊α⌋u_{y} + ⌊β⌋v_{y} = u_{y} + (r + 1)v_{y} = v_{y+1}, since α ∈ (1, 2) implies β ∈ (r + 1, r + 2).

For future reference, we give a direct proof of Corollary 13.

Proof. Put ν_{y} = b^{y}(n). Then

ν_{y+2} = ⌊β^{2}ν_{y} − β{βν_{y}}⌋ = ⌊(r + 2)βν_{y} − rν_{y} − β{βν_{y}}⌋
= (r + 2)ν_{y+1} − rν_{y} + ⌊(r + 2 − β){βν_{y}}⌋ = (r + 2)ν_{y+1} − rν_{y},

since, as β ∈ (r + 1, r + 2), it follows that r + 2 − β is in (0, 1).

4 The Narayana case

Here we consider a(n) := ⌊αn⌋ and b(n) := ⌊α^{3}n⌋, where α ≐ 1.46557 is the dominant zero of x^{3} − x^{2} − 1. Note that we do have 1/α + 1/α^{3} = 1.

The Narayana sequence (N_{k})_{k≥0} is the fundamental recurrence with characteristic polynomial x^{3} −x^{2} −1, i.e., with initial values 0, 0, 1. This sequence was used in the 14th century to model the population growth of a herd of cows [1]. Its OEIS number [18] is \underline{A078012}.

4.1 General results

Lemma 14. For all integers n ≥ 1, we have

a^{2}(n) = b(n) − n − e_{1}(n),
ba(n) = a(n) + b(n) − e_{2}(n),
ab(n) = a(n) + b(n) − e_{3}(n),
b^{2}(n) = a(n) + 3b(n) − n − e_{4}(n),

where the ranges of e_{1} and e_{2} are, respectively, {0, 1, 2} and {0, 1, 2, 3}, and the ranges of e_{3} and e_{4} are both {0, 1}.

Proof. Since α^{3} = α^{2} + 1, we see that

a^{2}(n) = ⌊α⌊αn⌋⌋ = ⌊α^{2}n − α{αn}⌋ = ⌊α^{3}n − α{αn}⌋ − n
= ⌊⌊α^{3}n⌋ + {α^{3}n} − α{αn}⌋ − n = b(n) − n + ⌊{α^{2}n} − α{αn}⌋.

Clearly −2 < −α < −α{αn} < {α^{2}n} − α{αn} < {α^{2}n} < 1, which explains that e_{1}(n) is either 0, 1 or 2. Similarly, ba(n) = ⌊α^{3}⌊αn⌋⌋ = ⌊α^{2}⌊αn⌋+⌊αn⌋⌋ = a(n)+⌊α^{3}n−α^{2}{αn}⌋ = a(n) + b(n) + ⌊{α^{3}n} − α^{2}{αn}⌋. Note that α^{2} > 2, so e_{2}(n) is potentially equal to 3. Also,

ab(n) = ⌊α(α^{3}n − {α^{3}n})⌋ = ⌊(α^{3} + α)n − α{α^{3}n}⌋

= a(n) + b(n) + ⌊{α^{3}n} + {αn} − α{α^{3}n}⌋ = a(n) + b(n) + ⌊{αn} + (1 − α){α^{2}n}⌋.

Noting that (1 − α){α^{2}n} ∈ (−1, 0) explains the range of e_{3}. Finally, as α^{6} = 3α^{3} + α − 1, we see that

b^{2}(n) = ⌊α^{3}(α^{3}n − {α^{3}n})⌋ = −n + ⌊3α^{3}n + αn − α^{3}{α^{3}n}⌋
= a(n) + 3b(n) − n + ⌊(3 − α^{3}){α^{3}n} + {αn}⌋.

Noting that (3 − α^{3}){α^{3}n} ∈ (−1, 0) explains the range of e_{4}.

It might be worth listing the exact expressions of the functions e_{i} found in the above proof. Namely,

e_{1}(n) = ⌈α{αn} − {α^{2}n}⌉
e_{2}(n) = ⌈α^{2}{αn} − {α^{2}n}⌉
e_{3}(n) = ⌈(α − 1){α^{2}n} − {αn}⌉
e_{4}(n) = ⌈(α^{3} − 3){α^{2}n} − {αn}⌉.

We observe that all values in the various ranges of the e_{i}’s are attained for some n. For instance, e_{2}(n) takes on the value 3, though only three times in the interval [1, 500].

Theorem 15. Let w = ℓ_{1} ∘ ℓ_{2} ∘ ⋯ ∘ ℓ_{s}, (s ≥ 1), where each ℓ_{i} is either a or b. Assume x and y are, respectively, the number of a’s and the number of b’s in w. Then,

w(n) = N_{x+3y−2} a(n) + N_{x+3y} b(n) − N_{x+3y−3} n − e_{w}(n),  (9)

where e_{w} is a nonnegative bounded integral function of n that depends on w and satisfies e_{w} ≤ 3pN_{p} with p = x + 3y.

Proof. The proof is by induction on ℓ ≥ 1 and analogous to that of Theorem 26, albeit less demanding, and also subsumed by the proof presented in Theorem 32. We only outline the bounds on e_{w} that Theorems 26, or 32, do not address. Assume w(n) satisfies (9) with p = x + 3y. Computing w(a(n)) with the expressions of a^{2}(n) and b(a(n)) from Lemma 14, we find

w(a(n)) = N_{(p+1)−2}a(n) + N_{p+1}b(n) − N_{(p+1)−3}n − e_{wa}(n),

where e_{wa}(n) = N_{p−2}e_{1}(n) + N_{p}e_{2}(n) + e_{w}(a(n)). Since 0 ≤ e_{1} ≤ 2 and 0 ≤ e_{2} ≤ 3 according to Lemma 14, we deduce, with the inductive hypothesis, that

0 ≤ e_{wa}(n) ≤ 2N_{p−2} + 3N_{p} + 3pN_{p} ≤ N_{p} + 2N_{p+1} + 3pN_{p} ≤ 3N_{p+1} + 3pN_{p+1} = 3(p + 1)N_{p+1}.

Similarly, e_{wb}(n) = e_{4}(n)N_{p−2} + e_{3}(n)N_{p} + e_{w}(b(n)). Clearly e_{wb}(n) ≤ N_{p+1} + 3pN_{p} ≤ 3(p + 3)N_{p+3}. Note that N_{−1} = 1 so e_{wa} and e_{wb} are both nonnegative even when p = 1.

The upper bound on the function e_{w}(n) can be substantially reduced for some subfamilies of sequences as the corollary below shows.

Corollary 16. We have b^{y}(n) = N_{3y−2}a(n)+N_{3y}b(n)−N_{3y−3}n−e_{(y)}(n) where 0 ≤ e_{(y)}(n) ≤ N_{3y−2}.

Proof. Theorem 15 gives that b^{y}(n) = N_{3y−2}a(n) + N_{3y}b(n) − N_{3y−3}n − e_{(y)}(n) for some nonnegative bounded function e_{(y)}. Thus,

b^{y+1}(n) = b^{y}(b(n)) = N_{3y−2}a(b(n)) + N_{3y}b^{2}(n) − N_{3y−3}b(n) − e_{(y)}(b(n)),

which, using Lemma 14 and the Narayana recursion N_{n} + N_{n−2} = N_{n+1}, yields b^{y+1}(n) = N_{3y+1}a(n)+N_{3y+3}b(n)−N_{3y}n−N_{3y}e_{4}(n)−e_{(y)}(b(n)). On the other hand, we have b^{y+1}(n) = N_{3y+1}a(n)+N_{3y+3}b(n)−N_{3y}n−e_{(y+1)}(n). Therefore, e_{(y+1)}(n) = N_{3y}e_{4}(n)+e_{(y)}(b(n)). Thus, e_{(y+1)}(n) − e_{(y)}(b(n)) ≤ N_{3y}. Hence,

e_{(y)}(b(n)) − e_{(y−1)}(b^{2}(n)) ≤ N_{3y−3}, …, e_{(2)}(b^{y−1}(n)) − e_{(1)}(b^{y}(n)) ≤ N_{3}.

But e_{(1)} = 0, so adding those inequalities yields e_{(y+1)}(n) ≤ ∑_{t=1}^{y} N_{3t}. An easy induction shows ∑_{t=1}^{y} N_{3t} = N_{3y+1}, which terminates our proof.

We are curious to know whether the sequences (b^{y}(n))_{y}, for fixed n, are linear recurrences as Corollaries 12 and 13 showed it is the case when β is of the form β = α + r, r an integer. Clearly, this will hold iff the sequences (e_{(y)}(n))_{y} of Corollary 16 are linear recurrences. The next subsection proves this is true when n = 1. However, before jumping to this next subsection, we fix an n ≥ 1, set τ_{y} := b^{y}(n) and mimic the second proof of Corollary 13 to establish that (τ_{y}), if not a linear recurrence, is nearly one, and with characteristic polynomial the minimal polynomial x^{3} − 4x^{2} + 3x − 1 of A := α^{3}. (See Lemma 18.)

Lemma 17. The sequence (τ_{y})_{y≥0} satisfies the relation

τ_{y+3} − 4τ_{y+2} + 3τ_{y+1} − τ_{y} = ξ_{y}, where ξ_{y} = ⌊(4 − A){Aτ_{y+1}} − A^{−1}{Aτ_{y}}⌋, (y ≥ 0).

Proof. Using A^{3} − 4A^{2} + 3A − 1 = 0, we find that

τ_{y+3} = ⌊Aτ_{y+2}⌋ = ⌊4τ_{y+2} + (A − 4)⌊Aτ_{y+1}⌋⌋
= 4τ_{y+2} + ⌊(A − 4)Aτ_{y+1} + (4 − A){Aτ_{y+1}}⌋.

But A^{2} − 4A = −3 + A^{−1} so τ_{y+3} = 4τ_{y+2} − 3τ_{y+1} + ⌊A^{−1}(Aτ_{y} − {Aτ_{y}}) + (4 − A){Aτ_{y+1}}⌋, which leads to the relation the lemma claims.

We see that ξ_{y} is either 0 or −1 because 4 − A ≐ 0.8521 and A^{−1} ≐ 0.3176, and seems more likely to be 0 than −1.

4.2 The sequence (b^{y}(1))_{y} = ⌊α^{3}⌊α^{3}⌊⋯ ⌊α^{3}⌋ ⋯⌋⌋⌋

In this subsection, we write τ_{y} for b^{y}(1), A for α^{3} and we define σ_{y} as the function

σ_{y} := N_{3y+3} − ∑_{k=0}^{⌊(3y−14)/12⌋} N_{3y−14−12k}.  (10)

We intend to prove that σ_{y} is a linear recurrence with characteristic polynomial equal to x^{4} − 1 times the minimal polynomial of A. This will give us a closed form for σ_{y} from which we can see that σ_{y+1} = ⌊α^{3}σ_{y}⌋ for y ≥ 20. Induction will then yield the equality of the sequences (σ_{y}) and (τ_{y}). The expression in (10) was found experimentally to match the first values of τ_{y}. Using PARI, we then had checked the coincidence of τ_{y} and σ_{y} for all y, 0 ≤ y ≤ 199.

Lemma 18. For any fixed integer t, the sequence (N_{3y+t})_{y} is a third-order recurrence with characteristic polynomial x^{3} − 4x^{2} + 3x − 1.

Proof. It suffices to verify that x^{3} − 4x^{2} + 3x − 1 = (x − α^{3})(x − β^{3})(x − γ^{3}), where β and γ are, besides α, the two other zeros of x^{3} − x^{2} − 1. Note that α + β + γ = 1, αβ + αγ + βγ = 0 and αβγ = 1. Thus, putting V_{n} = α^{n} + β^{n} + γ^{n}, we find that V_{0} = 3, V_{1} = 1, V_{2} = V_{1}^{2} − 2(αβ + αγ + βγ) = 1. Hence, V_{3} = V_{2} + V_{0} = 4. Now writing W_{n} for (αβ)^{n} + (αγ)^{n} + (βγ)^{n}, we see that (W_{n})’s characteristic polynomial is x^{3} − 0x^{2} + αβγ(α + β + γ)x − 1 = x^{3} + x − 1. Therefore, W_{3} = −W_{1} + W_{0} = 3 and, consequently, (x − α^{3})(x − β^{3})(x − γ^{3}) = x^{3} − V_{3}x^{2} + W_{3}x − 1 = x^{3} − 4x^{2} + 3x − 1, as we claimed.

Lemma 19. The sequence (σ_{y})_{y≥0} satisfies the recursion

σ_{y+3} − 4σ_{y+2} + 3σ_{y+1} − σ_{y} = ε_{y}, where ε_{y} = \begin{cases}0, & if y ≡ 0, 1 or 2 (mod 4); \\ −1, & if y ≡ 3 (mod 4). \end{cases}

In particular, (σ_{y}) is a seventh-order recurrence with characteristic polynomial (x^{4} − 1)(x^{3} − 4x^{2} + 3x − 1).

Proof. Define V_{y} as σ_{y+3} − 4σ_{y+2} + 3σ_{y+1} − σ_{y} for all y. By (10) and Lemma 18, we see that

\begin{matrix}−V_{y} = & ∑_{k=0}^{⌊(3y−5)/12⌋} N_{3y−5−12k} − 4 ∑_{k=0}^{⌊(3y−8)/12⌋} N_{3y−8−12k} \\ + & 3 ∑_{k=0}^{⌊(3y−11)/12⌋} N_{3y−11−12k} − ∑_{k=0}^{⌊(3y−14)/12⌋} N_{3y−14−12k}. \end{matrix}  (11)

By Lemma 18, if all four sums in the expression of −V_{y} above have the same number of terms, then V_{y} = 0. If I designates the set of all intervals J such that J ⊂ [m, m + 1), for some integer m, then those four sums will all have 1 + ⌊(3y − 14)/12⌋ terms iff the interval [(3y − 14)/12, (3y − 5)/12] ∈ I. Putting y = 4ℓ + r, 0 ≤ r ≤ 3, we see that

[(3y − 14)/12, (3y − 5)/12] ∈ I iff [(3r − 14)/12, (3r − 5)/12] ∈ I,

which occurs iff r = 1. Suppose y = 4ℓ. Then ⌊(3y − 5)/12⌋ = ⌊(3y − 8)/12⌋ = ⌊(3y − 11)/12⌋ = ℓ − 1 and ⌊(3y − 14)/12⌋ = ℓ − 2. Thus, using Lemma 18, we obtain that −V_{y} = N_{3y−5−12(ℓ−1)} − 4N_{3y−8−12(ℓ−1)} + 3N_{3y−11−12(ℓ−1)} = N_{7} − 4N_{4} + 3N_{1} = 4 − 4 + 0 = 0. Thus, V_{4ℓ} = 0 as well. Assume now y = 4ℓ+2. Then the first sum, i.e., ∑_{k=0}^{⌊(3y−5)/12⌋} N_{3y−5−12k} in (11), contains one more term than the three others. Hence, as ⌊(3y − 5)/12⌋ = ℓ, we see that −V_{y} = N_{3y−5−12ℓ} = N_{1} = 0. Finally, suppose y = 4ℓ + 3. Then ⌊(3y − 5)/12⌋ = ⌊(3y − 8)/12⌋ = ℓ, while ⌊(3y − 11)/12⌋ = ⌊(3y − 14)/12⌋ = ℓ − 1. Thus, −V_{y} = N_{3y−5−12ℓ} − 4N_{3y−8−12ℓ} = N_{4} − 4N_{1} = 1. Hence, V_{4ℓ+3} = −1, which ends the proof.

Since (σ_{y}) is a seventh-order recurrence with the zeros of its characteristic polynomial all identified, namely α^{3}, β^{3}, γ^{3} and all complex fourth roots of unity, we solved a 7 × 7 linear system and got a closed-form expression for σ_{y}. We found σ_{y} = I_{y} + r_{y}, where

\begin{aligned}I_{y} & := \frac{1}{117}(2N_{3y} + 103N_{3y+1} + 100N_{3y+2}), \\ r_{y} & := \frac{1}{4} − \frac{(−1)^{y}}{36} − \frac{3i + 2}{52}i^{y} + \frac{3i − 2}{52}(−i)^{y}, \end{aligned}  (12)

and i = \sqrt{−1}.

We may observe that α^{3}I_{y} − I_{y+1} can be made arbitrarily small, for all large enough y’s. Indeed, for t a fixed integer, N_{3y+t} is a linear combination of α^{3y}, β^{3y} and γ^{3y}. But, as the absolute values of β and γ are smaller than one, α^{3}N_{3y+t} − N_{3y+3+t} tends to 0 as y tends to infinity. The next lemma quantifies this observation.

Lemma 20. We have |E_{y}| < 6 · 10^{−5} for all y ≥ 20, where E_{y} := α^{3}I_{y} − I_{y+1}.

Proof. For all n ≥ 0, we have the closed-form expression

N_{n} = \frac{α^{n}}{f′(α)} + 2 Re(\frac{β^{n}}{f′(β)}),

where f′ is the derivative of f(x) = x^{3} − x^{2} − 1 and Re(z) stands for the real part of a complex z. Therefore, for t = 0, 1 or 2,

|α^{3}N_{3y+t} − N_{3y+3+t}| ≤ |2α^{3}Re(\frac{β^{3y+t}}{f′(β)}) − 2Re(\frac{β^{3y+3+t}}{f′(β)} )| ≤ 3α^{3} \frac{|β|^{3y}}{|f′(β)|}.

Hence,

|α^{3}I_{y} − I_{y+1}| ≤ \frac{2 + 103 + 100}{117} · \frac{3α^{3}}{|f′(β)|} · |β|^{3y} < 5.6 × |β|^{3y}.

Since |β| < 1 and 5.6 × |β|^{60} ≐ 0.0000581 ⋯, the lemma follows.

We are ready to prove that the two sequences are identical.

Theorem 21. For all y ≥ 0, τ_{y} = σ_{y}.

Proof. It is easy to check that r_{y} defined in (12) is of period 4 and that

r_{y} = \frac{1}{117} × \begin{cases}17, & if y ≡ 0 (mod 4); \\ 46, & if y ≡ 1 (mod 4); \\ 35, & if y ≡ 2 (mod 4); \\ 19, & if y ≡ 3 (mod 4). \end{cases}

(Thus, r_{y} + r_{y+1} + r_{y+2} + r_{y+3} = 1 for all y ≥ 0.)

We will need the differences Ar_{y} −r_{y+1} for all y’s so we compute them to three significant digits

Ar_{y} − r_{y+1} = 117^{−1} \begin{cases}17A − 46 \\ 46A − 35 \\ 35A − 19 \\ 19A − 17 \end{cases} ≐ \begin{cases}0.064, & if y ≡ 0 (mod 4); \\ 0.938, & if y ≡ 1 (mod 4); \\ 0.779, & if y ≡ 2 (mod 4); \\ 0.366, & if y ≡ 3 (mod 4). \end{cases}  (13)

Let y ≥ 20 be an integer. We suppose that τ_{k} = σ_{k} for all k’s, 0 ≤ k ≤ y, and proceed by induction. Thus, we need to show that τ_{y+1} = σ_{y+1}. Using our inductive hypothesis, we see that Aτ_{y} = Aσ_{y} = AI_{y} + Ar_{y} = I_{y+1} + E_{y} + Ar_{y} = (σ_{y+1} − r_{y+1}) + E_{y} + Ar_{y}. That is, Aτ_{y} = σ_{y+1} + (Ar_{y} − r_{y+1} + E_{y}). By Lemma 20, |E_{y}| < 6 · 10^{−5} and, by (13), 6 · 10^{−5} < Ar_{y} − r_{y+1} < 1 − 6 · 10^{−5}. Therefore, 0 < Ar_{y} − r_{y+1} + E_{y} < 1 and ⌊Aτ_{y}⌋ = σ_{y+1}. Since, by definition, τ_{y+1} = ⌊Aτ_{y}⌋, the inductive step is proved. As mentioned earlier the induction is well grounded as we checked that τ_{k} = σ_{k}, for all k, 0 ≤ k ≤ 199.

Remark 22. The four values of α^{3}r_{y} − r_{y+1} in (13) are the limit values, rounded to three decimals, of the fractional parts of α^{3}τ_{y}, as y increases. In fact, we found that for y = 20, 21, 22 and 23, those values are already, to three significant digits, equal to 0.064, 0.938, 0.779 and 0.366, respectively.

With ξ_{y} and ε_{y}, respectively, defined in Lemmas 17 and 19, we obtain the corollary

Corollary 23. For all y ≥ 0, we find that ξ_{y} = ε_{y}, i.e.,

⌊(4 − α^{3})\{α^{3}τ_{y+1}\} − α^{−3}\{α^{3}τ_{y}\}⌋ = \begin{cases}0, & if y ≡ 0, 1 or 2 (mod 4); \\ −1, & if y ≡ 3 (mod 4). \end{cases}

And, in return, we also have an expression for the remainder function e_{(y)}(1) of Corollary 16.

Corollary 24. For all y ≥ 0,

e_{(y)}(1) = ∑_{k=0}^{⌊(3y−14)/12⌋} N_{3y−14−12k}.

Proof. From Corollary 16, b^{y}(1) = a(1)N_{3y−2} + b(1)N_{3y} − N_{3y−3} − e_{(y)}(1). But a(1)N_{3y−2} + b(1)N_{3y} − N_{3y−3} = N_{3y−2} + 3N_{3y} − N_{3y−3} = N_{3y+1} + N_{3y} + N_{3y−1} = N_{3y+2} + N_{3y} = N_{3y+3}. Comparing with the expression of σ_{y} in (10) yields the corollary since σ_{y} = τ_{y} = b^{y}(1).

5 The (α, α^{4}) case with α^{4} − α^{3} − 1 = 0, α > 1

Here α is the dominant zero of x^{4} − x^{3} − 1. We find that α ≐ 1.38028. Thus, a(n) = ⌊nα⌋ and b(n) = ⌊nα^{4}⌋. We denote the fundamental sequence associated with x^{4} − x^{3} − 1 as H = (H_{k})_{k≥0}. That is, H_{0} = H_{1} = H_{2} = 0 and H_{3} = 1 with H_{n+4} = H_{n+3} + H_{n}, for all integers n. This is sequence \underline{A017898} in the OEIS [18].

a^{2}(n) = b(n) − n − ⌊\frac{n}{α}⌋ − e_{1}(n),
ba(n) = a(n) + b(n) − e_{2}(n),
ab(n) = a(n) + b(n) − e_{3}(n),
b^{2}(n) = a(n) + 4b(n) − 2n − ⌊\frac{n}{α}⌋ + e_{4}(n),

where the four e_{i}’s are bounded integral functions of n with ranges {0, 1, 2, 3} for e_{1} and e_{2}, {0, 1} for e_{3} and {−1, 0, 1} for e_{4}.

In fact,

e_{1}(n) = ⌈\{\frac{n}{α}\} + α\{αn\} − \{α^{3}n\}⌉
e_{2}(n) = ⌈α^{3}{αn} − {α^{3}n}⌉
e_{3}(n) = ⌈(α − 1){α^{3}n} − {αn}⌉
e_{4}(n) = ⌊(4 − α^{4})\{α^{3}n\} + \{αn\} − \{\frac{n}{α}\}⌋.

The least value of n for which e_{1}(n) = 3 is 113. The least n with e_{4}(n) = 1 is 47. We omit the proof of Lemma 25 as it is similar in spirit to that of Lemma 14.

Theorem 26. Let w = ℓ_{1} ∘ ℓ_{2} ∘ ⋯ ∘ ℓ_{s}, (s ≥ 1), where each ℓ_{i} is either a or b. Assume x and y are, respectively, the number of a’s and the number of b’s in w. Then w(n) equals

H_{x+4y−2}a(n) + H_{x+4y+1}b(n) − (H_{x+4y−3} + H_{x+4y−4})n − H_{x+4y−3}⌊\frac{n}{α}⌋ + e(n),

where e is a bounded integral function of n.

Proof. We carry out an inductive proof on the number of letters ℓ in the word w. By running the recursion defining the sequence H backwards, we find that H_{−3} = H_{−2} = 0 and H_{−1} = 1. Thus we easily check the result when ℓ = 1 and, using Lemma 25, for ℓ = 2. Assuming w is a word with ℓ ≥ 2 letters and the theorem holds for such words, we show the theorem still holds for wa and wb.

The inductive hypothesis gives that

wa(n) = H_{x+4y−2} a^{2}(n) + H_{x+4y+1} ba(n)
− (H_{x+4y−3} + H_{x+4y−4})a(n) − H_{x+4y−3}⌊\frac{a(n)}{α}⌋ + e(a(n)).

Note that ⌊\frac{a(n)}{α}⌋ = ⌊n − \frac{\{αn\}}{α}⌋ = n − 1. So using Lemma 25 and regrouping terms we obtain

wa(n) = (H_{x+4y+1} − H_{x+4y−3} − H_{x+4y−4}) a(n) + (H_{x+4y−2} + H_{x+4y+1}) b(n)
− (H_{x+4y−2} + H_{x+4y−3})n − H_{x+4y−2}⌊\frac{n}{α}⌋ + e′(n),

where e′(n) = H_{x+4y−3} − H_{x+4y−2}e_{1}(n) + H_{x+4y+1}e_{2}(n) + e(a(n)).

But H_{x+4y+1} − H_{x+4y−3} − H_{x+4y−4} = H_{x+4y} − H_{x+4y−4} = H_{x+4y−1} = H_{(x+1)+4y−2} and H_{x+4y−2} + H_{x+4y+1} = H_{x+4y+2} = H_{(x+1)+4y+1}. Therefore, wa(n) has the form claimed in the theorem.

Also by the inductive hypothesis,

wb(n) = H_{x+4y−2} ab(n) + H_{x+4y+1} b^{2}(n)
− (H_{x+4y−3} + H_{x+4y−4}) b(n) − H_{x+4y−3}⌊\frac{b(n)}{α}⌋ + e(b(n)).

Note that

⌊\frac{b(n)}{α}⌋ = ⌊\frac{(α^{5} − α)n − \{α^{4}n\}}{α}⌋ = b(n) − n + ⌊(1 − \frac{1}{α})\{α^{4}n\}⌋.

But (1 − 1/α){α^{4}n} ∈ (0, 1) so ⌊b(n)/α⌋ = b(n) − n.

Using Lemma 25, the identity ⌊b(n)/α⌋ = b(n) − n, and regrouping like-terms, we obtain

wb(n) = (H_{x+4y−2} + H_{x+4y+1})a(n)
+ (H_{x+4y−2} + 4H_{x+4y+1} − 2H_{x+4y−3} − H_{x+4y−4})b(n)
− (2H_{x+4y+1} − H_{x+4y−3})n − H_{x+4y+1}⌊\frac{n}{α}⌋ + e′′(n),

where e′′(n) = H_{x+4y−2}e_{2}(n)+H_{x+4y+1}e_{4}(n)+e(b(n)) is an integral and bounded function of n. Using the recursion for H, we obtain the expected coefficients for a(n), b(n), n and ⌊\frac{n}{α}⌋. For the coefficient of b(n), put t = x + 4y + 1. Then we check that H_{t+4} = 4H_{t} + H_{t−3} − 2H_{t−4} − H_{t−5}. It holds iff H_{t+3} = 3H_{t} + H_{t−3} − 2H_{t−4} − H_{t−5}. But

H_{t+3} = H_{t+2} + H_{t−1} = H_{t+1} + H_{t−1} + H_{t−2} = H_{t} + H_{t−1} + H_{t−2} + H_{t−3}.

Thus, the identity to prove holds iff H_{t−1} + H_{t−2} = 2H_{t} − 2H_{t−4} − H_{t−5}. But the latter is true as H_{t} − H_{t−4} = H_{t−1} and 2H_{t−1} − H_{t−5} = H_{t−1} + H_{t−2}.

6 The general case (α, α^{q}), (q ≥ 2)

Let q ≥ 2 be an integer. The polynomial f(x) := x^{q} − x^{q−1} − 1 possesses a simple dominant real zero α > 1 [2, Lemma 3]. Here, a(n) = ⌊nα⌋ and b(n) = ⌊nα^{q}⌋. We denote the fundamental sequence associated with f(x) as G = (G_{k})_{k≥0}. That is, G_{0} = G_{1} = ⋯ = G_{q−2} = 0 and G_{q−1} = G_{q} = ⋯ = G_{2q−2} = 1 as G_{t+q} = G_{t+q−1} + G_{t}.

Lemma 27. Let θ be a zero of x^{q} − x^{q−1} − 1. Then, for all integers n ≥ m, we find that

∑_{i=m}^{n} θ^{i} = θ^{n+q} − θ^{m+q−1}.

Proof. Summing the geometric series ∑_{i=m}^{n} θ^{i} yields the expression \frac{θ^{n+1}−θ^{m}}{θ−1} . But θ^{n+1} = θ^{n+q+1} − θ^{n+q} = θ^{n+q}(θ − 1) and θ^{m} = θ^{m+q−1}(θ − 1).

Lemma 28. For all integers n ≥ 1, we have

a^{2}(n) = b(n) − n − ⌊\frac{n}{α}⌋ − ⋯ − ⌊\frac{n}{α^{q−3}} ⌋ + O(1),
ba(n) = a(n) + b(n) + O(1),
ab(n) = a(n) + b(n) + O(1),
b^{2}(n) = a(n) + q b(n) − (q − 2) n − (q − 3)⌊\frac{n}{α}⌋ − ⋯ − ⌊\frac{n}{α^{q−3}} ⌋ + O(1).

Proof. By Lemma 27, ∑_{i=0}^{q−3} α^{−i} = ∑_{i=3−q}^{0} α^{i} = α^{q} − α^{2}. Hence,

a^{2}(n) = ⌊α^{2}n − α\{αn\}⌋ = ⌊α^{q}n − ∑_{i=0}^{q−3} \frac{n}{α^{i}} − α\{αn\}⌋

= b(n) − ∑_{i=0}^{q−3} ⌊\frac{n}{α^{i}} ⌋ + O(1).

Now ab(n) = ⌊α^{q}⌊αn⌋⌋ = ⌊(α^{q−1} +1)(αn−{αn})⌋ = a(n)+b(n)+O(1). A similar expansion also yields our claim for ba(n). The expression for b^{2}(n) will hold if α^{2q} = α+qα^{q}−∑_{i=0}^{q−3} α^{−i}− ∑_{i=0}^{q−2} α^{−i} − ⋯ − α^{−0}. That is, if α^{2q} = α + qα^{q} − ∑_{j=0}^{q−3} ∑_{i=3+j−q}^{0} α^{i}. Now, using Lemma 27 twice, we obtain

α + qα^{q} − ∑_{j=0}^{q−3} ∑_{i=3+j−q}^{0} α^{i} = α + qα^{q} − ∑_{j=0}^{q−3}(α^{q} − α^{2+j})
= α + 2α^{q} + (α^{2q−1} − α^{q+1}) = −(α^{q+1} − α^{q} − α) + (α^{q} + α^{2q−1})
= 0 + α^{2q}.

Remark 29. The third bounded function O(1) in the identity ab(n) = a(n) + b(n) + O(1) is ⌊(1 − α){α^{q}n} + {αn}⌋, so it is either 0 or −1.

Lemma 30. Let n ≥ m be integers. Then

∑_{i=m}^{n} G_{i} = G_{n+q} − G_{m+q−1}.

Proof. The derivative of f(x) only has 0 and (q −1)/q as zeros. Since neither 0, nor (q −1)/q is a zero of f, the zeros θ_{1}, …, θ_{q} of f(x) are simple. Thus, G_{i} is a linear combination of the θ_{t}^{i}, t = 1, …, q. Hence, the lemma is a direct consequence of Lemma 27.

Corollary 31. Let p ≥ 1, q ≥ 3 and 0 ≤ j ≤ q − 3 be integers. Then

∑_{3≤i≤q−j} G_{p−i} = G_{p+q−3} − G_{p+j−1}.

Proof. We note that ∑_{3≤i≤q−j} G_{p−i} = ∑_{i=p+j−q}^{p−3} G_{i} and apply Lemma 30.

Theorem 32. Let w be a composite function of some a’s and b’s. Putting p = x + qy, where x and y are, respectively, the number of a’s and the number of b’s in w, we find that, for all n ≥ 1,

w(n) = G_{p−2} a(n) + G_{p+q−3} b(n) − ∑_{0≤j≤q−3} c_{j}⌊\frac{n}{α^{j}} ⌋ + O(1),  (14)

where c_{j} = ∑_{3≤i≤q−j} G_{p−i}, or alternatively c_{j} = G_{p+q−3} − G_{p+j−1}.

Proof. Note that for q = 2, the sum ∑_{0≤j≤q−3} c_{j}⌊n/α^{j}⌋ is empty and equals 0 by convention. Hence, in that case, the theorem is implied by Theorem 2. Thus, assume q ≥ 3. Observe that, by Corollary 31, ∑_{3≤i≤q−j} G_{p−i} = G_{p+q−3} − G_{p+j−1}. We may proceed by induction on x + y as was done in Theorems 2, 5, 15 and 26. One checks the result for x + y = 1 directly. For instance, if w = a, then taking the function O(1) to be the null function and noting that G_{−1} = 1 and G_{−i} = 0, 2 ≤ i ≤ q − 1, we find that all coefficients c_{j} of (14) are zero so that G_{−1}a(n) + G_{q−2}b(n) − 0 + 0 is indeed a(n).

Now suppose (14) holds for some w with x + y ≥ 1 letters. Replacing n by a(n) in (14), using Lemma 28 to express a^{2}(n) and ba(n) and filling in some constant terms into the O(1) term, we find that

\begin{aligned}wa(n) & = G_{p−2}(b(n) − ∑_{0≤j≤q−3} ⌊\frac{n}{α^{j}} ⌋) + G_{p+q−3}(a(n) + b(n)) \\ & − ∑_{0≤j≤q−3} (G_{p+q−3} − G_{p+j−1})⌊\frac{a(n)}{α^{j}}⌋ + O(1). \end{aligned}  (15)

The coefficient of b(n) is G_{p−2} + G_{p+q−3} = G_{p+q−2} = G_{(p+1)+q−3}, while that of a(n) is G_{p+q−3} − (G_{p+q−3} − G_{p−1}) = G_{(p+1)−2}, as expected. Since ⌊n/α^{j−1}⌋ − ⌊a(n)/α^{j}⌋ is 0 or 1 for all j ≥ 1, the remaining terms are

−G_{p−2} ∑_{0≤j≤q−3} ⌊\frac{n}{α^{j}} ⌋ − ∑_{1≤j≤q−3} (G_{p+q−3} − G_{p+j−1})⌊\frac{n}{α^{j−1}} ⌋ + O(1).

But ∑_{1≤j≤q−3} (G_{p+q−3} − G_{p+j−1})⌊n/α^{j−1}⌋ = ∑_{0≤j≤q−4} (G_{p+q−3} − G_{p+j})⌊n/α^{j}⌋, so we see that the coefficient c_{j}(wa) of −⌊n/α^{j}⌋ in wa(n) is, for 0 ≤ j ≤ q − 4, equal to

(G_{p−2} + G_{p+q−3}) − G_{p+j} = G_{p+q−2} − G_{p+j} = G_{(p+1)+q−3} − G_{(p+1)+j−1},

while c_{q−3}(wa) = G_{p−2} = G_{(p+1)−3}, as expected.

Similarly, we expand wb(n), expressing ab(n) and b^{2}(n) with Lemma 28, to find that wb(n) may be written as

G_{p−2}(a(n) + b(n)) + G_{p+q−3}(a(n) + q b(n) − ∑_{0≤i≤q−3}(q − 2 − i)⌊\frac{n}{α^{i}} ⌋)

− ∑_{0≤j≤q−3} (G_{p+q−3} − G_{p+j−1})⌊\frac{b(n)}{α^{j}}⌋ + O(1).  (16)

The coefficient of a(n), G_{p−2} + G_{p+q−3}, is, as expected, equal to G_{(p+q)−2}. Given j between 1 and q − 3, and noting that

α^{q}n = (α^{q+1} − α)n = (α^{q+2} − α^{2} − α)n = ⋯ = (α^{q+j} − α^{j} − α^{j−1} − ⋯ − α)n, we see that, for all j ≥ 0,

⌊\frac{b(n)}{α^{j}}⌋ = b(n) − ∑_{0≤k≤j−1} ⌊\frac{n}{α^{k}} ⌋ + O(1).  (17)

Therefore the (natural) coefficient of b(n) in wb(n) is

G_{p−2} + q G_{p+q−3} − ∑_{0≤j≤q−3} (G_{p+q−3} − G_{p+j−1})

= G_{p−2} + 2G_{p+q−3} + ∑_{0≤j≤q−3} G_{p−1+j}

= G_{p−2} + 2G_{p+q−3} + (G_{p−1+2q−3} − G_{p+q−2})  (18)

= 2G_{p+q−3} + G_{p+2q−4} − (G_{p+q−2} − G_{p−2}) = G_{p+q−3} + G_{p+2q−3} − G_{p+q−3} = G_{p+2q−3},

as expected, where in (18) we used Corollary 31.

By (16) and (17), the coefficient c_{k}(wb) is

(q − 2 − k)G_{p+q−3} − ∑_{k+1≤j≤q−3}(G_{p+q−3} − G_{p+j−1})

= (q − 2 − k − (q − 3 − k))G_{p+q−3} + ∑_{j=k+1}^{q−3} G_{p−1+j}

= (G_{p+q−3} + G_{p+2q−4}) − G_{p+q+k−1}  (19)

= G_{(p+q)+q−3} − G_{(p+q)+k−1},

which is what we intended to prove. Again, in (19), we used Corollary 31.

Remark 33. The basis functions a(n), b(n), and the ⌊\frac{n}{α^{j}} ⌋, used to express w(n) in Theorem 32, are all integral, and so are their coefficients, but there is no uniqueness in this property. Other choices could have been made. For instance, in Lemma 28, we could have chosen to express a^{2}(n) as a(n) + ⌊\frac{n}{α^{q−2}} ⌋ − e(n), where e(n) = ⌈(α − 1)\{αn\} − \{n/α^{q−2}\}⌉ ∈ \{0, 1\}. Had we made this choice for a^{2}(n), the general expression of b^{y}(n), when q = 3, in Corollary 16, would have taken the form b^{y}(n) = (N_{3y−1} + N_{3y−6})a(n) + N_{3y−1}b(n) + N_{3y−3}⌊n/α⌋ + O(1).

7 Problems for future research

We provide some ideas for further investigation. These ideas only reflect how we see things at the moment and are probably more a measure of our ignorance than anything else.

Problem 34. Find other pairs of complementary Beatty sequences, preferably infinite families of such pairs (a_{s}(n), b_{s}(n)), and discover theorems comparable to Theorems 8 and 32 that express a word in a_{s} and b_{s} as nearly a linear combination of a_{s} and b_{s}.

(The referee pointed out the polynomials x^{q}−x^{q−1}−x−1 for q ≥ 3. Each such polynomial [2, Lemma 3] has a simple dominant zero α. In fact, for q = 3, α is a cubic Pisot number that can play a fundamental role in the construction of Rauzy fractals [14].)

The secondary question tackled in this paper of whether the sequences (b^{y}(n))_{y} are linear recurrences leads to a simple fundamental problem.

Problem 35. Let α > 1 be, say, a real algebraic integer of minimal polynomial P. Put f(n) := ⌊αn⌋. Fix an integer n ≥ 1 and define, for y a positive integer, u_{y} as f^{y}(n), where f^{y} is the y-fold composite function f ∘ ⋯ ∘ f.

1. Characterize those algebraic integers α for which the sequence (u_{y})_{y} is a linear recurrence of characteristic polynomial P for all choices of n.

2. Characterize those algebraic integers α for which the sequence (u_{y})_{y} is a linear recurrence for all choices of n. Is it necessarily true that the characteristic polynomial of (u_{y}) must be a multiple of P? Or that it must be of the form (x^{h} − 1)P for some h ≥ 0?

3. Suppose (u_{y})_{y} is a linear recurrence for n = 1. Does it follow that it is linear recurrent for all choices of n? If so, would there always be an annihilating polynomial common to all (u_{y}) for all values of n ≥ 1? How often would that common polynomial turn out to be the characteristic polynomial of (u_{y}) when n = 1?

Given a pair of complementary Beatty sequences (a, b), write A and B for the respective ranges of the functions a and b. For the Wythoff pair (a, b), we saw that b^{y}(1) = F_{2y+1}. Stolarsky [21, p. 441] observed that for all y ≥ 1, the pair V_{y} = (F_{2y}, F_{2y+1}) belongs to A × B and that the vectors V_{y} satisfy the second-order recursion V_{y+2} = 3V_{y+1} − V_{y}. Note that V_{y} = (⌊F_{2y−1}α⌋, ⌊F_{2y−1}α^{2}⌋) = (ab^{y−1}(1), b^{y}(1)). More generally, the vectors V_{y} = (ab^{y−1}(1), b^{y}(1)) satisfy the same second-order recurrence as (b^{y}(1))_{y} for all Beatty pairs of Section 3, where β = α + r, r ≥ 1. Indeed, by Corollary 13, (b^{y}(1))_{y} is a second-order recurrence, and one easily sees that ab^{y−1}(1) = b^{y}(1) − rb^{y−1}(1). In the Narayana case, we saw that (b^{y}(1))_{y} satisfies a 7th-order linear recurrence and it does seem experimentally that the vectors (ab^{y−1}(1), b^{y}(1)), all in A×B, satisfy the same 7th-order recursion. These various instances of the same phenomenon raise another problem

Problem 36. Characterize pairs of complementary Beatty sequences (a, b) such that the vectors V_{y} := (ab^{y−1}(1), b^{y}(1)) satisfy a linear recurrence relation.

In the Wythoff context, Stolarsky [21] discovered a sequence of vectors in A × B which satisfy a fourth-order linear recurrence with characteristic polynomial x^{4}−10x^{3}+16x^{2}−5x−1 coprime to x^{2} − 3x + 1. Later, Ridley [16] found infinitely many sequences of Wythoff pairs that satisfy fourth-order linear recurrences, one being a recurrence with characteristic polynomial x^{4} − x^{3} − 5x^{2} + 7x − 1.

Problem 37. Given a pair of complementary Beatty sequences (a, b) with α algebraic, are there general methods to generate sequences of vectors in A × B that satisfy higher-order linear recurrences?

The referee suggested another problem, not unrelated to Problem 35, which he illustrated with an example.

Problem 38. In §4, Lemma 17, we reach an identity of the form

∑_{k=0}^{m} c_{k}a_{n+k} = F (a_{n}, a_{n+1}),

where F is a floor function of a linear combination of fractional parts involving a_{n} and a_{n+1} which can only take finitely many values. As turned out the a_{n}’s of §4 satisfy a homogeneous linear recurrence, though of higher order. To be more specific, the characteristic polynomial has an ‘additional factor’ of x^{4} − 1. Can any general results of this nature be obtained?

A simple example of such recurrences is the following ‘almost Fibonacci’ recurrence

a_{n+2} = a_{n+1} + a_{n} + ⌊k{a_{n+1}α}⌋,

where k is a fixed positive integer, α = (1 + \sqrt{5})/2. Do the a_{n}’s satisfy homogeneous linear recurrences? If so, 1. what are the corresponding characteristic polynomials and 2. is the linear recurrence independent of the initial conditions? Computer experiments suggest that (for example) for k = 11 both (x^{3}−1)(x^{2}−x−1) and (x^{8}−1)(x^{2}−x−1) are possible depending upon the initial conditions. The same sort of thing seems true for k = 12 and 13 with possibly different such recurrences for different initial conditions. Perhaps there is always a recurrence whose characteristic polynomial has the form x^{2} − x − 1 or (x^{2} − x − 1)(x^{h} − 1) for some positive integer h?

8 Acknowledgments

We are thankful to the referee in three ways. He accepted our text as it was. He offered numerous references, with comments, to beautiful papers we were not aware of that may have connections with our text. Those appear at the end of the introduction and enrich the present paper. Finally, he suggested that we wrote an additional section for open investigations providing a couple of his own. We also thank Michel Dekking who, after reading the paper online, sent email on July 12th, 2017 to mention reference [6], where Theorem 2 had appeared before it reappeared in [9].

References

[1] J.-P. Allouche and T. Johnson, Narayana’s cows and delayed morphisms, Cahiers du GREYC, JIM 96 4 (1996) 2–7, available at

http://recherche.ircam.fr/equipes/repmus/jim96/actes/Allouche.ps.

[2] C. Ballot, On the constant in the average digit sum for a recurrence-based numeration, Unif. Distrib. Theory, 11 (2016), 125–150.

[3] S. Beatty, Problem 3173, Amer. Math. Monthly, 33 (1926), 159; 34 (1927), 159.

[4] M.-J. Bertin, A. Decomps-Guilloux, M. Grandet-Hugot, M. Pathiaux-Delefosse, and J.-P. Schreiber, Pisot and Salem Numbers, Birkhäuser Verlag, 1992.

[5] M. Boshernitzan and A. S. Fraenkel, Nonhomogeneous spectra of numbers, Discrete Math. 34 (1981), 325–327.

[6] L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Fibonacci representations, Fibonacci Quart., 10 (1972) 1–28.

[7] A. S. Fraenkel, Iterated floor function, algebraic numbers, discrete chaos, Beatty subsequences, semigroups, Trans. Amer. Math. Soc. 341 (1994), 639–664.

[8] A. S. Fraenkel, H. Porta, and K. B. Stolarsky, Some arithmetical semigroups, Progress in Math. 85 (1990), 255–264.

[9] C. Kimberling, Complementary equations and Wythoff sequences, J. Integer Sequences, 11 (2008), Article 08.3.3.

[10] C. Kimberling, Beatty sequences and Wythoff sequences, generalized, Fibonacci Quart., 49 (2011) 195–200.

[11] J. C. Lagarias, H. Porta, and K. B. Stolarsky, Asymmetric tent map expansions I: eventually periodic points, J. London Math. Soc. 47 (1993), 542–556.

[12] J. C. Lagarias, H. Porta, and K. B. Stolarsky, Asymmetric tent map expansions II, Illinois J. Math. 38 (1994), 574–588.

[13] H. A. Porta and K. B. Stolarsky, Wythoff pairs as semigroup invariants, Adv. in Math. 85 (1991), 69–82.

[14] G. Rauzy, Nombres algébriques et substitutions, Bull. Soc. Math. France, 110 (1982), 147–178.

[15] J. W. S. Rayleigh, The Theory of Sound, Vol. 1, 2nd edition, Macmillan, 1894.

[16] J. Ridley, Fourth order linear recurrences satisfied by Wythoff pairs, Ramanujan J. 5 (2001), 159–165.

[17] K. Scheicher, V. F. Sirvent, and P. Surer, Dynamical properties of the tent map, J. London Math. Soc. 93 (2016), 319–340.

[18] N. J. A. Sloane, The Online Encyclopedia of Integer Sequences, published electronically

    at http://oeis.org.

[19] C. J. Smyth. There are only eleven special Pisot numbers, Bull. London Math. Soc. 311 (1999), 1–5.

[20] K. Stolarsky, Beatty sequences, continued fractions, and certain shift operators, Canad. Math. Bull. 19 (1976), 473–482.

[21] K. Stolarsky, Fourth order linearly recurrent Wythoff pairs. Ramanujan J. 2 (1998), 441–448.

[22] W. A. Wythoff, A modification of the game of Nim, Nieuw Arch. Wisk., 2 (1905–07), 199–202.

2010 Mathematics Subject Classification: Primary 11B83; Secondary 11B37, 11B39. Keywords: Beatty sequence, Wythoff pair, integer part, linear recurrence.

(Concerned with sequences \underline{A078012}, \underline{A017898}.)

Received July 26 2016; revised versions received January 17 2017; January 28 2017. Published in Journal of Integer Sequences, January 28 2017. Minor revision, July 30 2017.

Return to Journal of Integer Sequences home page.