Journal of Integer Sequences, Vol. 3 (2000), Article 00.2.8

Abstract: Let S be the set of positive integers determined by these rules:

      1 is an element of S, and
      if x is an element of S, then 2x and 4x - 1 are elements of S.

Let s be the sequence of elements of S arranged in increasing order. The even terms of s occupy ranks-past-1 given by the sequence

      r = (1,3,4,6,8,9,11,12,14,16,...).

The same sequence gives the ranks of 0 's in the infinite Fibonacci word, 0100101001001010... . That is, r(n) = [n*τ], where τ = (1 + sqrt(5))/2.

Introduction

Let S be the "self-generating set" of positive integers determined by these rules:

      1 is an element of S, and
      if x is an element of S, then 2x and 4x-1 are elements of S.

We ask: how are the even numbers in S distributed among the odds? The question suggests arranging the elements of S in increasing order, which gives the sequence

(1)    s = (1,2,3,4,6,7,8,11,12,14,15,16,22,23,24,27,28,30,31,32,43,...).

In s, the evens, (2,4,6,8,12,...) and odds-past-1, (3,7,11,15,23,...), occupy positions of considerable interest. Numbering these positions to the right of the initial 1 yields ranks-past-1 sequences. Every positive integer lies in exactly one of these complementary sequences. In fact, these are the celebrated Beatty sequences known as the Wythoff sequences. The lower Wythoff sequence,

      r = (1,3,4,6,8,9,11,12,14,16, ...)

is given by r(n) = [n*τ], where τ is the golden mean, (1 + sqrt(5))/2. The complement of r,

      R = (2,5,7,10,13,15,18,20,23,26, ...),

called the upper Wythoff sequence, satisfies R(n) = n + [n*τ].

We note here, but do not use in the sequel, the fact that r and R give the ranks of 0 's and 1 's in the infinite Fibonacci word, 0100101001001010... , defined from an initial 0 by repeatedly substituting 01 for 0 and 0 for 1.

The entry in [2] for the sequence s, A052499, was contributed by Henry Bottomley, who notes that s(F(n + 3) - 1) = 2ⁿ, where F(k) denotes the kth Fibonacci number, given by the initial values and recurrence relation

      F(0) = 0, F(1) = 1, F(n + 2) = F(n) + F(n + 1) for n ≥ 0.

For further information about the other sequences mentioned above see A000201 (the lower Wythoff sequence), A001950 (the upper Wythoff sequence) and A003849 (the infinite Fibonacci word) in [2].

Main Result

A birds-eye view of the proof is this: establish that s can be generated in a manner analogous to a way of generating the sequence t of positive integers together with the nonnegative integer multiples of τ, arranged in increasing order, and then show that the evens-past-1 in s occupy the same positions as the positive integers in t.

Lemma 1. The sequence s in (1) is determined by its initial values and induction. We have:

(i) s(1) = 1, s(2) = 2, s(3) = 3, s(4) = 4, s(5) = 6, s(6) = 7.

(ii) Suppose for arbitrary n ≥ 3, m = 3,4,...,n and i = F(m + 3) - 1 that

(2)    s(i) = 2^m,

(3)    (s(i + 1),s(i + 2),...,s(i + F(m) - 1))

        = (2^m + s(F(m + 1)), 2^m + s(F(m + 1) + 1), ..., 2^m + s(F(m + 2) - 2)),

(4)    (s(i + F(m)), s(i + F(m) + 1), ..., s(i + F(m + 2) - 1))

        = (2^m + s(F(m + 2) - 1), 2^m + s(F(m + 2)), ..., 2^m + s(F(m + 3) - 2)).

Then equations (2)-(4) hold for all positive integers n ≤ 3.

Proof: Equations (2)-(4) clearly hold for n = 3. It then suffices to prove that they hold when m is replaced by m + 1. First, we shall show that the number of elements x in S that satisfy

(5)    2^{m + 1} ≤ x ≤ 2^{m + 2} - 1

is F(m + 3). By the induction hypothesis, the number of elements v in S such that

(6)    2^m ≤ v ≤ 2^{m + 1} - 1

is F(m + 2), and the number of elements u in S such that

(7)    2^{m - 1} ≤ u ≤ 2^{m - 1}

is F(m + 1). Each x in S is necessarily 2v for some v as in (6), or else 4u - 1 for some u as in (7), with one exception: 4*2^{m - 1} - 1 is not an x satisfying (5); on the other hand, 4*(2^m - 1) - 1 is an x in S satisfying (5), so that the number of x in S satisfying (5) is

(8)    F(m + 2) + (F(m + 1) - 1) + 1 = F(m + 3).

Write m + 1 for m in (3), obtaining F(m + 1) - 1 numbers

        2^{m + 1} + s(j), for j = F(m + 2), ..., F(m + 3) - 2.

If s(j) = 2u for u in S, then 2^{m + 1} + s(j) = 2*(2^m + u), an element of S since 2^m + u is an element of S. If s(j) = 4v - 1 for v in S, then 2^{m + 1} + s(j) = 4*(2^{m - 1} + v) - 1 is an element of S since 2^{m - 1} + v is an element of S. Hence the numbers on the right-hand side of (3) are all in S.

Write m + 1 for m in (4), obtaining F(m + 2) numbers

      2^{m + 1} + s(j), for j = F(m + 3), ..., F(m + 4) - 2.

As just proved in connection with (3), all these numbers are in S.

Finally, 2^{m + 1} = 2*2^m, in S. To summarize, equation (8) counts the F(m + 3) numbers in S that appear on the left-hand sides of (2)-(4), and the F(m + 3) numbers on the right-hand sides of (2)-(4) have been proved to be in S. It is now noted that, by induction, these numbers on the right-hand sides are listed in increasing order, hence in the same order as those on the left-hand sides.

We turn now to a comparable development of the lower Wythoff sequence. Let N = {1,2,3,...} and T = N UNION {k*τ : k = 0,1,2,...}. Let t be the sequence of elements of T arranged in increasing order.

Lemma 2. The sequence t is determined by its initial values and induction. We have:

(i) t(1) = 0, t(2) = 1, t(3) = τ, t(4) = 2, t(5) = 3, t(6) = 2*τ.

(ii) Suppose for arbitrary n>3 and m = 1,2,...,n and i = F(m + 3) - 1 that

(2')    t(i) = F(m + 2) - 1,

(3')    (t(i + 1), t(i + 2), ..., t(i + F(m) - 1)) =

        (w(F(m + 1)) + t(F(m + 1)), w(F(m + 1) + 1) + t(F(m + 1) + 1), ..., w(F(m + 2) - 2) + t(F(m + 2) - 2)),

(4')    (t(i + F(m)), t(i + F(m) + 1), ..., t(i + F(m + 2) - 1)) =

        (w(F(m + 2) - 1) + t(F(m + 2) - 1), w(F(m + 2)) + t(F(m + 2)), ..., w(F(m + 3) - 2) + t(F(m + 3) - 2)),

where w(j) = F(m + 1) if t(j) is an integer, and w(j) = τ*F(m) if t(j) = k*τ for some integer k,

for j = F(m + 1), ..., F(m + 3) - 2. Then equations (2)-(4) hold for all positive integers n>3.

Proof: It is easy to check that equations (2')-(4') hold for n = 3. It suffices to prove that they hold when m is replaced by m + 1. Following the method of proof of Lemma 1, we shall show that the number of elements x in T that satisfy

(5')   F(m + 3) - 1 ≤ x ≤ F(m + 4) - 1

is F(m + 3). By induction hypothesis, the number of y in T such that

(6')   F(m + 2) - 1 ≤ y ≤ F(m + 3) - 1

is F(m + 2), and the number of y in T such that

(7')   F(m + 1) - 1 ≤ y ≤ F(m + 2) - 1

is F(m + 1). Therefore the number of x in T satisfying (5') is

        F(m + 2) + F(m + 1) = F(m + 3).

We have t(0) < t(1) < t(2) < t(3) < t(4) < t(5) < t(6) < t(7). Continuing inductively, we shall prove that the F(m + 3) numbers as formulated on the right-hand sides of (2')-(4'), which are clearly in T, are in increasing order. Let t(j) < t(j + 1) be neighboring terms as in (3') and (4') taken together; i.e., F(m + 1) ≤ j ≤ F(m + 3) - 3. We consider four cases:

   Case i: t(j) in N and t(j + 1) in N. Here,

      w(j) + t(j) = F(m + 1) + t(j) < F(m + 1) + t(j + 1) = w(j + 1) + t(j + 1).

   Case ii: t(j) in N and t(j + 1) = k*τ for some k in N. If m is odd, then w(j) = F(m + 1) < τ*F(m) = w(j + 1), so that

(9)    w(j) + t(j) = F(m + 1) + t(j) < τ*F(m) + k*τ = w(j + 1) + t(j + 1).

If m is even, we must work harder: F(m + 1)/F(m) is a convergent to τ, hence a best approximation (Lang [1], 1 - 11), which means that

(10)   F(m + 1) - τ*F(m) < k*τ - [k*τ] for 1 ≤ k ≤ F(m + 1) - 1.

Hence, in particular, F(m + 1) - τ*F(m) < t(j + 1) - t(j) since t(j + 1) = k*τ for some k as in (10), and so (9) holds.

   Case iii: t(j) = k*τ for some k in N and t(j + 1) in N. An argument analogous to that for case (ii) yields

      w(j) + t(j) = τ*F(m) + k*τ < F(m + 1) + t(j + 1) ≤ w(j + 1) + t(j + 1).

   Case iv: t(j) = k*τ and t(j + 1) = (k + 1)*τ for some k in N. This cannot happen, since

      k*τ < [(k + 1)*τ] ≤ (k + 1)*τ.

Thus the numbers of the right-hand sides of (2')-(4') are identical to and listed in the same order as those on the left-hand sides.

THEOREM. The ranks-past-1 sequence for even terms of s is given by r(n) = [n*τ].

Proof: Lemma 1 establishes that the numbers on the right-hand sides of (2)-(4) are, in the same order,

      s(i), s(i + 1), ..., s(i + F(m + 2) - 1),

where i = F(m + 3) - 1, for m = 3,4,..., and s(i) = 2^m. Since s(i + F(m + 2) - 1) = 2^{m + 1} - 1, we have

s(i + F(m + 2) - 1) < s(F(m + 4) - 1) < 2^{m + 1}.

Therefore the numbers on the right-hand sides of (2)-(4), together with the six initial values, account for the whole sequence, inductively.

Let ρ(n) be the rank in s, after the initial 1, of the nth even term. The six initial terms (1,2,3,4,6,7) yield ρ(1) = 1, ρ(2) = 3, ρ(3) = 4, in agreement with r(1) = 1, r(2) = 3, r(3) = 4 as the ranks-past-0 of integers in t = (0, 1, τ, 2, 3, 2*τ, ...).

In order to prove that ρ(n) = r(n) for all n ≥ 3, we refer again to the inductive definitions (2)-(4) and (2')-(4'). Let

      s(j(1)), s(j(2)), ..., s(j(q)),     ( j(1) < j(2) < ... < j(q))

represent the evens satisfying (2)-(4). Then the evens satisfying (5) are

(11)   2^m + s(j(1)), 2^m + s(j(2)), ..., 2^m + s(j(q)),

and these have ranks determined by the subscripts on the left-hand sides of (2)-(4). Assume as an induction hypothesis that

      t(j(1)), t(j(2)), ..., t(j(q))

are the integers satisfying (2')-(4'). Then the integers satisfying (5') are

      F(m + 1) + t(j(1)), F(m + 1) + t(j(2)), ..., F(m + 1) + t(j(q)).

They have ranks determined by the subscripts on the left-hand sides of (2')-(4'). Since these subscripts exactly match those of (11), we have ρ = r.

The predecessors-past-0 of the nth integer in t are the integers 1,2,...,n together with the [n/τ] irrationals τ, 2*τ, ..., [n/τ]*τ so that ρ(n) = n + [n/τ] = [n*τ]. Since r = ρ, we conclude that r(n) = [n*τ] for n = 1,2,3, ... .

References

[1] Lang, Serge. Introduction to Diophantine Approximations, Addison-Wesley, 1966.

[2] Sloane, N. J. A. On-line Encyclopedia of Integer Sequences, published electronically at http://oeis.org.

 

(Concerned with sequences A000045 A000201 A001950 A003849 A052499. )

Received October 4 2000; published in Journal of Integer Sequences December 5 2000.