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

University of Evansville

1800 Lincoln Avenue

Evansville, IN 47722

Email address: ck6@evansville.edu

**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 2*x*and 4*x*- 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.

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 2*x* and 4*x*-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^{n},
where *F*(*k*) denotes the *k*th 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].

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 2*v* for some *v* as
in (6), or else 4*u* - 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*) = 2*u* 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*) = 4*v* - 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

(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 *n*th 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 *n*th 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, ... .

[1] Lang, Serge.Introduction to Diophantine Approximations,Addison-Wesley, 1966.[2] Sloane, N. J. A.

On-line Encyclopedia of Integer Sequences, published electronically athttp://oeis.org.

(Concerned with sequences A000045 A000201 A001950 A003849 A052499. )

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

Return to Journal of Integer Sequences home page