Lucas Representations of Positive Integers

Clark Kimberling Department of Mathematics University of Evansville Evansville, Indiana 47722 USA

                      ck6@evansville.edu

Abstract Various kinds of representations of positive integers using nonconsecutive Lucas numbers are used to define arrays related to the Wythoff array. The columns of these arrays, or their order arrays, partition the positive integers. Limiting densities are found for numbers whose Lucas representations all have the same least term.

1 Introduction

Throughout, the set of positive integers is denoted by ℕ, and i, k, m, n, u represent elements of ℕ. The golden ratio, (1 + \sqrt{5})/2, is denoted by τ. The sequence (L_{n}) of Lucas numbers is given by L_{0} = 2, L_{1} = 1, and L_{n} = L_{n−1} + L_{n−2} for n ≥ 2. In 1972, Carlitz, Scoville, and Hoggatt [2] proved the following uniqueness theorem for representations of positive integers as sums of nonconsecutive Lucas numbers.

Theorem 1. Every n has a unique representation in exactly one of these two forms:

n = L_{k_{1}} + ⋯ + L_{k_{u}} + L_{0} (or n = 2),  (1)
where k_{i} − k_{i+1} ≥ 2 for 1 ≤ i ≤ u − 1, k_{u} ≥ 3  (2)

or

n = L_{k_{1}} + ⋯ + L_{k_{u}}  (3)
where k_{i} − k_{i+1} ≥ 2 for 1 ≤ i ≤ u − 1, k_{u} ≥ 1.  (4)

Following the notation in [2], let B_{0} be the sequence of numbers n given by (1) and (2), and let B_{k} be the sequence given by (3) and (4); e.g.,

B_{0} = (2, 6, 9, 13, 17, 20, 24, 27, 31, 35, 38, 42, 46, 49, ⋯)
B_{1} = (1, 5, 8, 12, 16, 19, 23, 26, 30, 34, 37, 41, 45, 48, ⋯)
B_{2} = (3, 10, 14, 21, 28, 32, 39, 43, 50, 57, 61, 68, 75, 79, ⋯).

In general, B_{k} consists of all n such that the least term in (1), or (3), is L_{k}. Clearly the sequences B_{k} partition ℕ.

The representations in Theorem 1 are patterned after Zeckendorf representations, which we review as follows. The sequence (F_{n}) of Fibonacci numbers is given by F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2. The Zeckendorf representation of n is the unique sum

n = F_{k_{1}} + ⋯ + F_{k_{u}}  (5)
where k_{i} − k_{i+1} ≥ 2 for i = 1 ⋯ u − 1, k_{u} ≥ 2.  (6)

For every n, the greedy algorithm can be used to find the successive terms in all three representations (1) and (2), (3) and (4), and (5) and (6).

Historically, the Zeckendorf representation dates back to Zeckendorf’s work as early as 1939, but he did not submit the result for publication until April, 1972; remarkably, his reference section includes the 1972 papers [1] and [2]. Zeckendorf’s theorems [8] are quoted here:

THÉORÈME I.a. Tout nombre naturel N peut être représenté par une somme de nombres de Fibonacci distincts non consécutifs. THÉORÈME I.b. Pour tout nombre naturel, cette somme est unique. THÉORÈME II.a. Tout nombre naturel N peut être représenté par une somme de nomberes de Lucas distincts non consécutifs. THÉORÈME II.b. La représenté des nombres naturels par une somme de nombres de Lucas non consécutifs est unique, sauf pour les nombres L_{2v+1} + 1.

Aside from the Lucas representations in Theorem 1, another kind of Lucas representation is given by Luo [5], in which some but not all n have a unique representation; indeed those n having more than one representation have exactly two representations.

The main purpose of this article can now be stated: to partition ℕ, or some subset of ℕ, as the set of columns of certain arrays (as in Tables 2-5) obtained from various kinds of Lucas representations, and to consider corresponding order arrays, densities, and limiting densities. These results can be compared to similar results already well known for the Wythoff array.

2 Wythoff array and Lucas-Wythoff arrays

In 1980, Morrison defined the Wythoff array (w(n, k)) by the formulas

w(n, 1) = ⌊⌊nτ⌋τ⌋ and w(n, 2) = ⌊⌊nτ⌋τ^{2}⌋

together with the Fibonacci recurrence

w(n, k) = w(n, k − 1) + w(n, k − 2) for k ≥ 3.

The Wythoff array, which shows all the winning pairs for the Wythoff game, has been widely studied; see, for example, the Comments and Links at \underline{A035513} in [7] and “Wythoff visions”

[3] In Theorem 4, we state and verify a formula for w(n, k) that appears elsewhere (e.g., [4]) without proof. We begin with lemmas that account for the first two columns of the Wythoff array. The notation {x} is used for the fractional part of a real number x, defined by {x} = x − ⌊x⌋.

Lemma 2. If n ≥ 1, then ⌊⌊nτ⌋τ⌋ = ⌊nτ⌋ + n − 1.

Proof. Since the fractional part {nτ} of nτ is in (0, 1), we have

⌊n − {nτ}(τ − 1)⌋ = n − 1.

The identity τ^{2} = τ + 1 then gives

n − 1 = ⌊nτ^{2} − nτ − {nτ}(τ − 1)⌋
= ⌊(nτ − {nτ})(τ − 1)⌋
= ⌊⌊nτ⌋(τ − 1)⌋
= ⌊⌊nτ⌋τ⌋ − ⌊nτ⌋.

Lemma 3. ⌊⌊nτ⌋τ^{2}⌋ = 2⌊nτ⌋ + n − 1.

Proof. Using Lemma 2, we have

⌊⌊nτ⌋τ^{2}⌋ = ⌊⌊nτ⌋(τ + 1)⌋
= ⌊⌊nτ⌋τ⌋ + ⌊nτ⌋
= (⌊nτ⌋ + n − 1) + ⌊nτ⌋.

Theorem 4. The Wythoff array is given by

w(n, k) = ⌊nτ⌋F_{k+1} + (n − 1)F_{k}  (7)

for n ≥ 1, k ≥ 1.

Proof. For every n, equation (7) holds for k = 1 and k = 2, by the two lemmas. Assume (7) for all n and arbitrary k ≥ 2. Then

w(n, k + 1) = w(n, k) + w(n, k − 1)
= ⌊nτ⌋F_{k+1} + (n − 1)F_{k} + ⌊nτ⌋F_{k} + (n − 1)F_{k−1}
= ⌊nτ⌋(F_{k+1} + F_{k}) + (n − 1)(F_{k} + F_{k−1})
= ⌊nτ⌋F_{k+2} + (n − 1)F_{k+1};

so that inductively, (7) holds for all k.

1 2 3 5 8 13 21 34 55 89 …
4 7 11 18 29 47 76 123 199 322
6 10 16 26 42 68 110 178 288 466
9 15 24 39 63 102 165 267 432 699
12 20 32 52 84 136 220 356 576 932
14 23 37 60 97 157 254 411 665 1076
⋮

Table 1: Wythoff array

1 2 3 4 7 11 18 29 47 76 …
5 6 10 15 25 40 65 105 170 275
8 9 14 22 36 58 94 152 246 398
12 13 21 33 54 87 141 228 369 597
16 17 28 44 72 116 188 304 492 796
⋮

Table 2: 1st Lucas-Wythoff array

Referring to Table 1, the Fibonacci numbers and Lucas numbers occupy rows 1 and 2, respectively, and every row satisfies the recurrence r_{n} = r_{n−1} + r_{n−2}, and every n occurs exactly once. Furthermore, for all k, column k consists of those numbers m having F_{k+1} as least term in the Zeckendorf representation ((5) and (6)), as proved in [4]. Indeed, the Zeckendorf array as defined in [4] is identical to the Wythoff array.

We now define the 1st Lucas-Wythoff array, (r(n, k)), by columns: (column 1) = B_{1}, (column 2) = B_{0}, and, for k ≥ 2, (column k) = B_{k}. See Table 2.

The inclusion of column 2 ensures that every n in ℕ occurs (exactly once) in the array and that all rows and columns are strictly increasing. However, column 2 interrupts the Fibonacci row recurrence seen in the Zeckendorf array. Here, instead, we have r(n, 4) = r(n, 1)+r(n, 3) for all n, and r(n, k) = r(n, k − 1) + r(n, k − 2) for n ≥ 1 and k ≥ 5. Deleting column 2 results in the 2nd Lucas-Wythoff array, (r^{∗}(n, k)), for which we have a formula much like (7), shown in Theorem 5. See Table 3.

Theorem 5. The 2nd Lucas-Wythoff array is given by

r^{∗}(n, k) = ⌊nτ⌋L_{k} + (n − 1)L_{k−1},  (8)

for n ≥ 1, k ≥ 1.

Proof. Let b(n, k) denote the nth term of the sequence B_{k}. First we prove that b(n, k) = w(n, k − 2) + w(n, k) for k ≥ 1. Following [2], let

a(n) = ⌊τn⌋, b(n) = ⌊τ^{2}n⌋, and let

1 3 4 7 11 18 29 47 76 123 …
5 10 15 25 40 65 105 170 275 445
8 14 22 36 58 94 152 246 398 644
12 21 33 54 87 141 228 369 597 966
16 28 44 72 116 188 304 492 796 1288
19 32 51 83 134 217 351 568 919 1487
23 39 62 101 163 264 427 691 1118 1809
⋮

Table 3: 2nd Lucas-Wythoff array

A_{2t} = (ab^{t−1}a(n) : n ≥ 1, t ≥ 1)
A_{2t+1} = (b^{t−1}a(n) : n ≥ 1, t ≥ 1),

where concatenation of functions abbreviates composition. As proved in [1], we have w(n, k) = A_{k}. Likewise [2],

B_{0} = (a^{2}(n) + n : n ≥ 1)
B_{1} = (a^{2}(n) + n − 1 : n ≥ 1)
B_{2t} = (b^{t−1}a(n) + b^{t}a(n) : n ≥ 1, t ≥ 1)
B_{2t+1} = (ab^{t−1}a(n) + ab^{t}a(n) : n ≥ 1, t ≥ 1).

Thus,

B_{2t} = A_{2t−1} + A_{2t+1} = (w(n, 2t − 1) + (w(n, 2t + 1))
B_{2t+1} = A_{2t} + A_{2t+1} = (w(n, 2t) + w(n, 2t + 1)),

so that b(n, k) = w(n, k − 2) + w(n, k) for all n and k ≥ 3. By Theorem 4,

b(n, k) = ⌊nτ⌋F_{k−1} + (n − 1)F_{k−2} + ⌊nτ⌋F_{k+1} + (n − 1)F_{k}
= ⌊nτ⌋(F_{k−1} + F_{k+1}) + (n − 1)(F_{k−2} + F_{k})
= ⌊nτ⌋L_{k} + (n − 1)L_{k−1}.

The first rows of Table 3 provide some interesting examples involving the Wythoff array (W, as in Table 1):

Row 1 ∼ row 2 of W, as they have in common (4, 7, …) Row 2 ∼ row 16 of W, with common tail (40, 65, …) Row 3 ∼ row 9 of W, with common tail (22, 36, …) Row 4 ∼ row 13 of W, with common tail (33, 54, …) .

Because every positive Fibonacci sequence is represented in W, every row of both Lucas-Wythoff arrays must, in the sense indicated by the examples, be tail-equivalent to a row of W. We leave open further investigation of this equivalence, which can be cast as follows: in each row of either Lucas-Wythoff array, where does a Wythoff pair first occur? (After the first pair, all subsequent pairs in a row are Wythoff pairs.)

3 Admissible representations

The requirement k_{u} ≥ 1 in connection with the representation (4) shows that the number 2 is disallowed as a term. If 2 is allowed, then uniqueness is lost; e.g., 5 can be represented by both 4 + 1 and 3 + 2. Luo [5] proved that if 2 is allowed, then each n has at most two representations, so that any n having at least two representations must have exactly two. We shall identify them explicitly.

Definition 6. A representation

n = L_{k_{1}} + ⋯ + L_{k_{u}}  (9)

is an admissible representation of n if

k_{i} − k_{i+1} ≥ 2 for 1 ≤ i ≤ u − 1, k_{1} ≥ 0.  (10)

Note that, unlike (4), in (10), the index k_{1} can be 0. Clearly, both of the representations ((1) and (2)) and ((3) and (4)) are admissible.

Theorem 7. If n = L_{k_{1}} + ⋯ + L_{k_{u}}, where u ≥ 2, k_{u} = 1, and k_{u−1} is odd, then n has exactly two admissible representations.

Proof. Suppose that k_{1} = 1 and k_{2} is odd. We consider two cases.

Case 1: u = 2. Here,

n = 1 + L_{2i+1} for some i ≥ 1.

As a first induction step, if i = 1, then n = 5 = 1 + 4 = 2 + 3, two representations. Assume for arbitrary i ≥ 1 that n = 1 + L_{2i+1} has a second admissible representation, n = s, where 1 is not a term of s, and the greatest term of s is less than L_{2i+1}. Then

1 + L_{2i+3} = 1 + L_{2i+1} + L_{2i+2}  (11)
= s + L_{2i+2}.  (12)

This shows that 1 + L_{2i+3} has two admissible representations.

Case 2: u ≥ 3. Here, suppose that

n′ = 1 + L_{2i+1} + s′  (13)

where i ≥ 1 and the Lucas representation ((3) and (4)) of s′ has least term ≥ L_{2i+3}. Then by (12), a second admissible representation of n′ is s + L_{2i+2}.

For both cases, if n or n′ has a third admissible representation, then one of the representations ((1) and (2)) or ((3) and (4)) is not unique, contrary to Theorem 1. Therefore, numbers of the forms in cases 1 and 2 have exactly two admissible representations.

Theorem 8. (Converse of Theorem 7) If n = L_{k_{1}} + ⋯ + L_{k_{u}} has two admissible representations, then one of them has u ≥ 2, k_{u} = 1, and k_{u−1} odd.

Proof. Suppose that n has two admissible representations,

n = L_{k_{1}} + ⋯ + L_{k_{u}} = L_{i_{1}} + ⋯ + L_{i_{v}}.

By Theorem 1, either k_{u} = 0 or i_{v} = 0; assume the latter, so that

n = L_{i_{1}} + ⋯ + L_{i_{v}−1} + 2, where i_{v} − 1 ≥ 3; i.e., L_{i_{v−1}} ≥ 4.

By the uniqueness of ((2) and (4)), we must have i_{v} − 1 = 2 because of (2), leading to two cases.

Case 1: n = 3 + 2, so that n = 4 + 1, as asserted.

Case 2: n = w + 3 + 2, where, by (3) and (4), the number w has a representation (3) with least term L_{m} for some m ≥ 4. If m ≥ 5, then

n = ⋯ + L_{m} + 3 + 2 = ⋯ + L_{m} + 4 + 1, as asserted.

This leaves the possibility that m = 4, so that n = w′ +7+3+2, where, again by (3) and (4), the number w′ has a representation (3) with least term L_{m} for some m ≥ 6. This procedure can be continued, leading to the asserted form of representation in fewer than 2i_{1} steps.

Examples:

12 = 11 + 1 = 7 + 3 + 2
16 = 11 + 4 + 1 = 11 + 3 + 2
19 = 18 + 1 (unique)
30 = 29 + 1 = 18 + 7 + 3 + 2
34 = 29 + 4 + 1 = 29 + 3 + 2

Definition 9. The Luo-Lucas array, (ℓ(n, k)), consists of the numbers that have exactly two admissible representations: column k of the array is the increasing sequence of numbers n whose representation (3) has least term L_{2k+1} + 1.

5 12 30 77 200 522 1365 3572 …
16 41 106 276 721 1886 4936 12921
23 59 153 399 1043 2729 7143 18699
34 88 229 598 1564 4093 10714 28048
45 117 305 797 2085 5457 14285 37397
52 135 352 920 2407 6300 16492 43175
⋮

Table 4: Luo-Lucas array

8 19 48 124 323 844 2208 …
26 66 171 446 1166 3051 7986
37 95 247 645 1687 4415 11557
55 142 370 967 2530 6622 17335
73 189 493 1289 3373 8829 23113
84 218 569 1488 3894 10193 26684
⋮

Table 5: Dual of Luo-Lucas array

Theorem 10. The Luo-Lucas array is given by

ℓ(n, k) = 1 + ⌊nτ⌋L_{2k+1} + (n − 1)L_{2k}, n ≥ 1, k ≥ 1.  (14)

Proof. Column k of (ℓ(n, k)) has first term m(1, k) = L_{2k+1} + 1, and all the terms thereafter are, in order, of the form m(1, k) + U, where U ranges through the positive integers u having least term L ≥ L_{2k+3} in the Lucas-Wythoff representation of U. These numbers are, in the same order, the numbers in column 2k + 1 of the 2nd Lucas-Wythoff array. Therefore, by Theorem 5, equation (14) holds.

Every number in the Luo-Lucas array is in column 1 of the Lucas-Wythoff array 3. The remaining numbers in column 1, excluding the initial 1, form a sequence (d(n, k)) given by

d(n, k) = (8, 19, 26, 37, 48, 55, 66, …),

whose terms can be naturally arranged to form a dual, (ℓ^{∗}(n, k)) of the Luo-Lucas array, given by

ℓ^{∗}(n, k) = 1 + ⌊nτ⌋L_{2k+2} + (n − 1)L_{2k+1}, n ≥ 1, k ≥ 1.

4 Order arrays

Following the definition at \underline{A333029}, suppose that (a(n, k)), for n ≥ 1, k ≥ 1, is an array of distinct numbers. If each a(n, k) is replaced by its position when all the numbers a(n, k) are ordered by <, the resulting array is the order array of (a(n, k)).

In this section, we shall see that the order array of the 2nd Lucas-Wythoff array is the Wythoff array. A proof depends on several lemmas. The first three involve properties of the Fibonacci numbers that follow readily from the fact that the fractions F_{k+1}/F_{k} are the convergents to τ. Proofs of these three are omitted. Lemma 11. If k ≥ 3 is odd, then 0 < τF_{k−2} − F_{k−1} + 1. Lemma 12. If k ≥ 3 is odd, then F_{k−2} − 1 < τ(F_{k−3} + 1). Lemma 13. If k ≥ 3 is even, then −1 ≤ τF_{k−3} − F_{k−2} < 1.

Let β(n, k) be the number of numbers i in B_{0} such that i ≤ r^{∗}(n, k). Several lemmas will be used to prove the following equation, to be used in proving Theorem 19:

β(n, k) = ⌊nτ⌋F_{k−1} + (n − 1)F_{k−2},  (15)

for n ≥ 1 and k ≥ 1, where F_{0} = 0 and F_{−1} = 1. Lemma 14. If n ≥ 1 and k ≥ 3, then β(n, k) = ⌊\frac{⌊nτ⌋L_{k}+(n−1)L_{k−1}+1}{τ+2}⌋. Proof. The numbers in B_{0} = (B(m)), for m ≥ 1, are given by

B(m) = ⌊τ⌊τm⌋⌋ + m
= ⌊mτ⌋ + m − 1 + m by Lemma 2,

so that we seek the number of numbers m, hence the greatest such m, satisfying

⌊mτ⌋ + 2m − 1 ≤ ⌊nτ⌋L_{k} + (n − 1)L_{k−1} + 1 + {mτ}.

This inequality can be recast as

m(τ + 2) ≤ ⌊nτ⌋L_{k} + (n − 1)L_{k−1} + 1 − {mτ},

and dividing by τ + 2 finishes the proof. Lemma 15. The equation (15) holds for k = 1 and all n. Proof.

0 < 1 − {nτ} < τ + 2
(n − 1)(τ + 2) < nτ + {nτ} + 2n − 1 < n(τ + 2)
n − 1 < \frac{nτ + \{nτ\} + 2n − 1}{τ + 2} < n,

so that (15), the right-hand side of which is n − 1 when k = 1, holds.

Lemma 16. The equation (15) holds for k = 2 and all n. Proof. First, τ⌊nτ⌋ < τ^{2}n = (τ + 1)n, and also

n = nτ^{2} − nτ < (τ − 1)(nτ + {nτ}) + τ + 2, so that
τ⌊nτ⌋ < ⌊nτ⌋ + n < τ⌊nτ⌋ + τ + 2.

Adding 2⌊nτ⌋ and dividing by τ + 2 give

⌊nτ⌋ < \frac{3⌊nτ⌋ + n}{τ + 2} < ⌊nτ⌋ + 1,

so that (15), the right-hand side of which is ⌊nτ⌋ when k = 2, holds. Lemma 17. If k ≥ 3, then β(n, k) = ⌊\frac{(n−1+3⌊nτ⌋)F_{k−1}+(2n−2+⌊nτ⌋)F_{k−1}+1}{τ+2}⌋. Proof. This results readily by substituting L_{k} = 3F_{k−1} + F_{k−2} and L_{k−1} = 2F_{k−2} + F_{k−1} into the formula in Lemma 14. Lemma 18. The equation (15), for k ≥ 3 and all n, is equivalent to

0 < τF_{k−2} − F_{k−1} + 1 + (F_{k} − τF_{k−1}){nτ} < τ + 2.  (16)

Proof. Equation (15) and Lemma 17 give the following inequalities equivalent to (15):

⌊nτ⌋F_{k−1} + (n − 1)F_{k−2} < \frac{(n − 1 + 3⌊nτ⌋)F_{k−1} + (2n − 2 + ⌊nτ⌋)F_{k−1} + 1}{τ + 2}
< ⌊nτ⌋F_{k−1} + (n − 1)F_{k−2} + 1

Multiplying by τ + 2 and then expanding the products and canceling like terms leave

τ⌊nτ⌋F_{k−1} + τ(n − 1)F_{k−2} < (⌊nτ⌋ + n − 1)F_{k−1} + ⌊nτ⌋F_{k−2} + 1
< τ⌊nτ⌋F_{k−1} + τ(n − 1)F_{k−2} + τ + 2,

which is successively equivalent to each of these:

0 < ((1 − τ){nτ} − 1)F_{k−1} + (τ + {nτ})F_{k−2} + 1 < τ + 2
0 < τF_{k−2} − F_{k−1} + 1 + (F_{k−2} + (1 − τ)F_{k−1}){nτ} < τ + 2
0 < τF_{k−2} − F_{k−1} + 1 + (F_{k} − τF_{k−1}){nτ} < τ + 2.

Theorem 19. The order array of the 2nd Lucas-Wythoff array (Table 3 is the Wythoff array.

Proof. By Lemma 18, we must prove that (16) holds for k ≥ 3 and arbitrary n. (For k = 1 and k = 2, the proof is already established by Lemmas 15 and 16.)

Case 1: k odd. Here, F_{k} − τF_{k−1} > 0, so that by Lemma 11,

0 < τF_{k−2} − F_{k−1} + 1 < τF_{k−2} − F_{k−1} + 1 + (F_{k} − τF_{k−1}){nτ}.

Also,

τF_{k−2} − F_{k−1} + 1 + (F_{k} − τF_{k−1}){nτ} < τF_{k−2} − F_{k−1} + 1 + (F_{k} − τF_{k−1}),

and this last expression simplifies to F_{k−2} − τF_{k−3} + 1, which by Lemma 12 is < τ + 2.

Case 2: k even. Here, F_{k} − τF_{k−1} < 0, so that by Lemma 13,

0 < F_{k−2} − τF_{k−3} + 1 < τF_{k−2} − F_{k−1} + 1 + F_{k} − τF_{k−1}
< τF_{k−2} − F_{k−1} + 1 + (F_{k} − τF_{k−1}){nτ}.

Also,

τF_{k−2} − F_{k−1} + 1 + (F_{k} − τF_{k−1}){nτ} < τF_{k−2} − F_{k−1} + 1 + (F_{k} − τF_{k−1}).

Abbreviating this last expression as E, the desired inequality E < τ + 2 is equivalent to

F_{k} − F_{k−1} − 1 < τ(F_{k−1} − F_{k−2}),

which is equivalent to F_{k−2} − 1 ≤ τF_{k−3}, which holds by Lemma 13.

The reader may wish to prove the following proposition.

Theorem 20. The Wythoff difference array, \underline{A080164}, is the order array of both the Luo-Lucas array (Table 4) and its dual (Table 5).

5 Densities and limiting densities

Suppose that s = (s_{k}) for k ≥ 1, is a sequence in ℕ. Define

c(s, m) = number of numbers in s that are ≤ m,

and define the density of s in [1, m], by

D(s, m) = \frac{m}{c(s, m)}.  (17)

In order to estimate densities of column sequences of the Wythoff array, (w(n, k)), we start with a lemma:

Lemma 21. For every n and k, w(n + 1, k) − w(n, k) ∈ {F_{k+2}, F_{k+3}}.

Proof. By Theorem 4,

w(n + 1, k) − w(n, k) = ⌊(n + 1)τ⌋F_{k+1} + nF_{k} − (⌊nτ⌋F_{k+1} + (n − 1)F_{k})
= (τ + {(n + 1)τ} − {nτ})F_{k+1} + F_{k}
= δF_{k+1} + F_{k}, where δ ∈ {1, 2}.

Example 22. For fixed n and all k, let s_{k} = w(n, k). The density

D(w(n, k), m),

which is the proportion of numbers in column k (that is, numbers whose Zeckendorf representation has F_{k+1} as least term) of the Wythoff array that are ≤ m, is estimated as follows. Let n be the number satisfying

w(n, k) ≤ m < w(n + 1, k).

Then by Lemma 21,

\frac{n}{w(n, k) + F_{k+3}} ≤ \frac{n}{w(n + 1, k)} ≤ D(w(n, k), m) = \frac{n}{m} < \frac{n}{w(n, k)}.

Applying Theorem 4 and dividing by n lead to a limiting density:

lim_{n→∞} D(w(n, k)) = \frac{1}{τF_{k+1} + F_{k}} .

Since the columns of (w(n, k)) partition ℕ, we have

∑_{k=1}^{∞} \frac{1}{τF_{k+1} + F_{k}} = 1.

Example 23. We turn now to the second column, B_{0} = (r(2, k)) = \underline{A188378}, of the 1st Lucas-Wythoff array:

D(r(2, k), n) = \frac{n}{⌊τ⌊nτ⌋⌋ + n},

so that the limiting density is

\frac{1}{τ^{2} + 1} = \frac{2}{5 + \sqrt{5}} ≈ 27.64%.

Next, consider the 2nd Lucas-Wythoff array, (r^{∗}(n, k)).

Lemma 24. For every n and k, r^{∗}(n + 1, k) − r^{∗}(n, k) ∈ {L_{k+1}, L_{k+2}}.

Proof. By Theorem 5,

r^{∗}(n + 1, k) − r^{∗}(n, k) = ⌊(n + 1)τ⌋L_{k} + nL_{k−1} − (⌊nτ⌋L_{k} + (n − 1)L_{k−1})
= (τ + {nτ})L_{k} − L_{k−1}
= δL_{k} + L_{k−1}, where δ ∈ {1, 2}.

Example 25. For fixed n and all k, let s_{k} = r^{∗}(n, k). The density

D(r^{∗}(n, k), m),

which is the proportion of numbers in column k (that is, numbers whose Lucas representation has L_{k} as least term) of the 2nd Lucas-Wythoff array that are ≤ m, is estimated as follows. Let n be the number satisfying

r^{∗}(n, k) ≤ m < r^{∗}(n + 1, k).

Then by Lemma 24,

\frac{n}{r^{∗}(n, k) + L_{k+2}} ≤ \frac{n}{r^{∗}(n + 1, k)} ≤ D(r^{∗}(n, k), m) = \frac{n}{m} < \frac{n}{r^{∗}(n, k)}.

Applying Theorem 4 and dividing by n lead to a limiting density:

lim_{n→∞} D(r^{∗}(n, k)) = \frac{1}{τL_{k} + L_{k−1}} .

Since the columns of (r^{∗}(n, k)) partition ℕ − B_{0}, we have, as a corollary of Example 23,

∑_{k=1}^{∞} \frac{1}{τL_{k} + L_{k−1}} = 1 − \frac{1}{τ^{2} + 1} ≈ 72.36%.

Example 26. Recall the Luo-Lucas array, (ℓ(n, k)). Following the proof of Lemma 24, it is easy to find that

ℓ(n + 1, k) − ℓ(n, k) ∈ {L_{2k+2}, L_{2k+3}}

and

∑_{k=1}^{∞} \frac{1}{τL_{2k+1} + L_{2k}} = \frac{1}{3τ + 1} = \frac{3\sqrt{5} − 5}{10} ≈ 17.08%,

which agrees with the limit obtained in a different manner by Luo [5].

Example 27. Finally, recall the dual of the Luo-Lucas array, (ℓ^{∗}(n, k)). As in Example 26,

ℓ^{∗}(n + 1, k) − ℓ^{∗}(n, k) ∈ {L_{2k+2}, L_{2k+3}}

and

∑_{k=1}^{∞} \frac{1}{τL_{2k+2} + L_{2k+1}} = 1 − \frac{2}{\sqrt{5}} ≈ 10.55%.

6 Concluding conjectures

In addition to the open question posed at the end of Section 2, we recall conjectures from \underline{A214979} and \underline{A214981.}

1. Let I(n) = {1, 2, …, n}. Let U(n) be the number of terms in the unique greedy Lucas representations of the numbers in I(n), and let V (n) be the number of terms in the Zeckendorf representations of I(n). Then V (n) ≥ U(n) for all n, and V (n) = U(n) for infinitely many n.

2. Let S = (1, 2, 3, 4, 5, 7, 8, 11, 13, 18, …) be the sequence, in increasing order, of all Fibonacci and Lucas numbers. Let W (n) be the number of terms in the greedy Srepresentations of the numbers in I(n) (as in \underline{A214981}). Then the limit of V (n)/W (n) exists and is the interval (1.2, 1.4).

7 Acknowledgment

The author thanks the referee for helpful suggestions.

References

[1] Leonard Carlitz, Richard Scoville, and V. E. Hoggatt, Jr., Fibonacci representations, Fibonacci Quart. 10 (1972) 1–28. Available at https://www.fq.math.ca/Scanned/10-1/

carlitz1.pdf.

[2] Leonard Carlitz, Richard Scoville, and V. E. Hoggatt, Jr., Lucas representations, Fibonacci Quart. 10 (1972) 29–42, 70, 112. Available at https://www.fq.math.ca/

Scanned/10-1/carlitz2-a.pdf.

[3] Eric Duchêne, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, Wythoff visions, in Games of No Chance 5, Math. Sci. Res. Inst. Publ. 70, Cambridge University Press, 2019, pp. 35–87.

[4] Clark Kimberling, The Zeckendorf array equals the Wythoff array, Fibonacci Quart. 33

(1995) 3–8. Available at https://www.fq.math.ca/Scanned/33-1/kimberling.pdf.

[5] David C. Luo, Proportion of nonunique Zeckendorf related partitions in the Lucas sequence, preprint, 2020. Available at https://arxiv.org/pdf/2004.08316.pdf; to appear in Fibonacci Quart..

[6] David R. Morrison, A Stolarsky array of Wythoff pairs, in A Collection of Manuscripts Related to the Fibonacci Sequence, The Fibonacci Association, 1980. Available at http://

web.math.ucsb.edu/~drm/papers/stolarsky.pdf.

[7] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available

   at https://oeis.org/.

[8] Edouard Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Liège 41 (1972) 179–182.

2010 Mathematics Subject Classification: Primary 11A63; Secondary 11B39. Keywords: Lucas sequence, Fibonacci sequence, Lucas representation, Zeckendorf representation, Wythoff array.

(Concerned with sequences \underline{A000027}, \underline{A000032}, \underline{A000045}, \underline{A000201}, \underline{A001622}, \underline{A001950}, \underline{A003622}, \underline{A035513}, \underline{A080164}, \underline{A188378}, \underline{A214979}, \underline{A214981}, \underline{A333029}, \underline{A335499}, and \underline{A335500}.) For sequence numbers of several rows and columns of the Wythoff array, see \underline{A035513}.

Received June 14 2020; revised version received September 29 2020; October 13 2020. Published in Journal of Integer Sequences, October 15 2020.

Return to Journal of Integer Sequences home page.