Complementary Equations and Wythoff Sequences

Clark Kimberling Department of Mathematics University of Evansville 1800 Lincoln Avenue Evansville, IN 47722 USA

                      ck6@evansville.edu

Abstract

The lower Wythoff sequence a = (a(n)) and upper Wythoff sequence b = (b(n)) are solutions of many complementary equations f(a, b) = 0. Typically, f(a, b) involves composites such as a(a(n)) and a(b(n)), and each such sequence is treated as a binary word (e.g., aa and ab). Conversely, each word represents a sequence and, as such, is a linear combination of a, b, and 1, in which the coefficients of a and b are consecutive Fibonacci numbers. For example, baba = 3a + 5b − 6.

1 Introduction

An example of a complementary equation is

a(a(n)) = b(n) − 1,  (1)

where it is given that the sequences a and b are complementary—that is, they are strictly increasing sequences of positive integers, and every positive integer is in exactly one of the sequences. Given the initial value a(1) = 1, equation (1) has as a unique solution the lower Wythoff sequence, a(n) = ⌊τn⌋ , or equivalently, the upper Wythoff sequence, b(n) = ⌊τ^{2}n⌋ , where τ = (1 + \sqrt{5})/2.

Equation (1) can be abbreviated as aa = b − 1. Here, the concatenation aa (which will also be written as a^{2}) represents composition, and the reduced notation provides a convenient way to express complementary equations, such as ab = a + b, ba = a + b − 1, and b^{2} = a + 2b.

The Wythoff sequences are solutions of these equations. The main purpose of this article is to show that every word of the sort suggested by a^{2}, ab, ba, and b^{2} lends itself to a simple complementary equation having Wythoff solutions.

Suppose

w = l_{1}l_{2} ⋯ l_{k}

is a word on the two-symbol alphabet {a, b}. We shall use w to denote not only the word but also the sequence (w(n)) defined as w = w_{k}, where

w_{1}(n) = l_{1}(n), w_{2}(n) = w_{1}(l_{2}(n)), …, w_{k}(n) = w_{k−1}(l_{k}(n)).

Call k = k(w) the length of w. Let m = m(w) be the number of occurrences of the letter b in w, and call m the weight of w.

Regarding notation, set braces { } denote fractional parts as well as sets; N denotes the set of positive integers, and the Fibonacci sequence (F_{n}) is defined by F_{1} = 1, F_{2} = 1, and F_{n} = F_{n−1} + F_{n−2} for n ≥ 3.

In the following four lemmas, a and b denote the Wythoff sequences. These symbols may also be regarded as representing a general pair of complementary sequences defining a complementary equation; in this case, given the initial value a(1) = 1, a solution of the equation is the Wythoff solution, but there are, for some of the equations, also other solutions.

Possibly these lemmas all appear in other settings, but proofs are included here for the sake of completeness.

Lemma 1. a^{2} = b − 1.

Proof. For every n in N,

0 < (τ − 1){τn} < 1,

so that

−1 = ⌊{τn} − τ{τn}⌋
= ⌊τn − ⌊τn⌋ − τ{τn}⌋
= ⌊τn − τ{τn}⌋ − ⌊τn⌋ ,

so that ⌊τn⌋ = ⌊τn − τ{τn}⌋ + 1. Then using b(n) = ⌊τn⌋ + n,

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

Lemma 2. ab = a + b.

Proof. Adapting a proof in [5], for every n in N we have

a(b(n)) = ⌊τ ⌊τ^{2}n⌋⌋
= ⌊τn + τ ⌊τn⌋⌋
= n + ⌊2τn − τn − n + τ ⌊τn⌋⌋
= 2 ⌊τn⌋ + n + ⌊2τn − 2 ⌊τn⌋ − τn − n + τ ⌊τn⌋⌋
= ⌊τn⌋ + ⌊τ^{2}n⌋ + ⌊2τn − 2 ⌊τn⌋ − τ^{2}n + τ ⌊τn⌋⌋
= a(n) + b(n),

because

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

Lemma 3. ba = a + b − 1. Proof. For every n in N,

b(a(n)) = b(⌊τn⌋) = ⌊τ ⌊τn⌋⌋ + ⌊τn⌋
= a(a(n)) + a(n),

and now Lemma 1 applies. Lemma 4. b^{2} = a + 2b. Proof. Using Lemma 2,

b(b(n)) = a(b(n)) + b(n) = a(n) + b(n) + b(n).

Lemmas 1-4 show the four words w of length 2 as sequences which, as solutions of complementary equations, are simple linear combinations of a, b, and 1. This result will be extended to longer words in the next section.

2 Main Theorem on Wythoff sequences

Lemmas 1-4 enable a proof that every word, as a sequence, is a linear combination of a, b, and 1 in which the coefficients of a and b are consecutive Fibonacci numbers. Theorem 5. Let w = l_{1}l_{2} ⋯ l_{k} with length k ≥ 2 and weight m. Then, as a sequence,

w = F_{k+m−2}a + F_{k+m−1}b − c,  (2)

where c ≥ 0, invariant of n, is given by c = F_{k+m+1} − w(1).

Proof. For k = 2, there are four words w, namely a^{2}, ab, ba, b^{2}, and by Lemmas 1-4, the complementary equation (2) holds for each of these. As an induction hypothesis, assume for arbitrary k ≥ 2 and every word

w = l_{1}l_{2} ⋯ l_{k}  (3)

that (2) holds. Let

w′ = l_{1}l_{2} ⋯ l_{k}l_{k+1}

be an arbitrary word of length k + 1, and let k′ and m′ denote the length and weight of w′.

Case 1. l_{k+1} = a, so that k′ = k + 1 and m′ = m. We have w′ = wa where w is as in (3). The induction hypothesis is that

w(υ) = F_{k+m−2}a(υ) + F_{k+m−1}b(υ) − c

for every υ in N. Thus for any n in N, we put υ = a(n) :

w′(n) = w(a(n)) = F_{k+m−2}a(a(n)) + F_{k+m−1}b(a(n)) − c,

so that

w′ = F_{k+m−2}a^{2} + F_{k+m−1}ba − c
= F_{k+m−2}(b − 1) + F_{k+m−1}(a + b − 1) − c
= F_{k+m−1}a + F_{k+m}b − c − F_{k+m}
= F_{k′+m′−2}a + F_{k′+m′−1}b − c − F_{k+m}.

Case 2. l_{k+1} = b, so that k′ = k + 1, m′ = m + 1 and w′ = wb, and

w′(n) = w(b(n)) = F_{k+m−2}a(b(n)) + F_{k+m−1}b(b(n)) − c,

which is

w′ = F_{k+m−2}ab + F_{k+m−1}b^{2} − c
= F_{k+m−2}(a + b) + F_{k+m−1}(a + 2b) − c
= F_{k+m}a + F_{k+m+1}b − c
= F_{k′+m′−2}a + F_{k′+m′−1}b − c.

Thus, (2) is proved, and clearly c is invariant of n. Put n = 1 to find from (2) that

c = −w(1) + a(1)F_{k+m−2} + b(1)F_{k+m−1}
= F_{k+m+1} − w(1).

That c ≥ 0 follows inductively from the observations that c ≥ 0 in each of Lemmas 1-4 and that in both cases above, as we pass from w to w′, the constant c passes to a new constant c′ ≥ c.

3 Tables and examples

Table 1. Words of length 2

aa = b − 1  ba = a + b − 1
ab = a + b  bb = a + 2b

Sequences in [7] corresponding to the words in Table 1 are \underline{A003622}, \underline{A003623}, \underline{A035336}, and \underline{A101864}, respectively.

Table 2. Words of length 3

aaa = a + b − 2  abb = 2a + 3b
aab = a + 2b − 1  bab = 2a + 3b − 1
aba = a + 2b − 2  bba = 2a + 3b − 3
baa = a + 2b − 3  bbb = 3a + 5b

Sequences in [7] corresponding to the words in Table 2 are \underline{A134859}, \underline{A134864}, \underline{A035337}, \underline{A134861}, \underline{A134862}, \underline{A134863}, \underline{A035338}, and \underline{A134864}, respectively.

Table 3. Words of length 4

aaaa = a + 2b − 4  abba = 3a + 5b − 5
aaab = 2a + 3b − 2  baba = 3a + 5b − 6
aaba = 2a + 3b − 4  bbaa = 3a + 5b − 8
abaa = 2a + 3b − 5  abbb = 5a + 8b
baaa = 2a + 3b  babb = 5a + 8b − 1
aabb = 3a + 5b − 1  bbab = 5a + 8b − 3
abab = 3a + 5b − 2  bbba = 5a + 8b − 8
baab = 3a + 5b − 3  bbbb = 8a + 13b

Example 6. a^{k} = F_{k−2}a + F_{k−1}b − F_{k+1} + 1 for all k in N. Example 7. b^{k} = F_{2k−2}a + F_{2k−1}b for all k in N.

4 The constant c

The constant c in Theorem 5 is not easily written out in general. However, we can gain some insights using the following theorem.

Theorem 8. Suppose, as in Theorem 5, that w = F_{k+m−2}a + F_{k+m−1}b − c.

Then for i ≥ 0,

wa^{2i} = F_{k+m+2i−2}a + F_{k+m+2i−1}b − c − i ; ∑_{h=1}F_{k+m+2h}  (4)

wa^{2i+1} = F_{k+m+2i−1}a + F_{k+m+2i}b − c − F_{k+m+2i} − i ; ∑_{h=1}F_{k+m+2h}  (5)
wb^{i} = F_{k+m+2i−2}a + F_{k+m+2i−1}b − c.  (6)

Proof. Each equation is easily proved by induction on i.

As every word is a concatenation of subwords covered by (4)-(6), it follows that the constant c in (2) is a sum of Fibonacci numbers, each appearing at most twice, as in (5), where F_{k+m+2i} occurs twice.

Corollary 9. Suppose w is a word. In the representation (2), c = 0 if and only if w = b^{i+1} or w = ab^{i} for some i ≥ 1.

Proof. The assertion is clearly true for words of length 1. By Lemmas 1-4, among words of length 2, we have c = 0 only for w = b^{2} and w = ab. The remaining cases now follow from (6).

5 Columns of the Wythoff array

Let W denote the Wythoff array [1, 8, 9], for which the entry in row n, column h, is

W (n, h) = (n − 1)F_{h} + ⌊nτ⌋ F_{h+1}.

Words w, taken as sequences, have close connections to columns of W.

Theorem 10. Column h of W is given by

w_{h} := \{ \begin{matrix}ab^{(h−1)/2}a & if h is odd \\ b^{h/2}a & if h is even. \end{matrix}

Proof. By Theorem 5, for all h and n in N,

w_{h}(n) = F_{h−1}a(n) + F_{h}b(n) − F_{h}
= F_{h−1} ⌊nτ⌋ + F_{h}(⌊nτ⌋ + n − 1)
= (F_{h−1} + F_{h}) ⌊nτ⌋ + (n − 1)F_{h}
= (n − 1)F_{h} + ⌊nτ⌋ F_{h+1}
= W (n, h).

The next theorem tells that the sequences in Corollary 9 are ordered unions of columns of W.

Theorem 11. For all h in N,

ab^{h−1} = ordered ∪{w_{2j−1} : j = h, h + 1, h + 2, ...}

and

b^{h} = ordered ∪{w_{2j} : j = h, h + 1, h + 2, ...}.

Proof of Theorem 11 is left to the reader, who may wish to prove also, regarding all words not covered by Theorems 10 and 11, that every word a^{2}w′, as a sequence, is a subsequence of column 1 of W, that every baw′ is a subsequence of column 2, that every abaw′ is a subsequence of column 3, that every bbaw′ is a subsequence of column 4, and so on.

6 Concluding remarks

Some complementary equations having Wythoff solutions have been presented. Others, such as ab − ba = 1, can be written easily by inspecting Tables 1-3. Most of these equations have not only the Wythoff solutions, but also others. For example, the equation ab = a + b has the sequence (2n − 1) as a solution. One wonders if general solutions can be obtained for this and other complementary equations, and not only for the initial value a(1) = 1. The interested reader may wish to consult [1] (especially Chapters 7 and 9) and [2, 3, 4, 5, 6].

References

[1] J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge University Press, 2003.

[2] A. S. Fraenkel, The bracket function and complementary sets of integers, Canad. J. Math. 21 (1969) 6–27.

[3] A. S. Fraenkel, Complementing and exactly covering sequences, J. Combin. Theory Ser. A 14 (1973) 8–20.

[4] A. S. Fraenkel, Complementary systems of integers, Amer. Math. Monthly 84 (1977) 114–115.

[5] A. S. Fraenkel and C. Kimberling, Generalized Wythoff arrays, shuffles and interspersions, Discrete Math. 126 (1994) 137–149.

[6] C. Kimberling, Complementary equations, J. Integer Sequences 10 (2007), Article 07.1.4.

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

   http://www.research.att.com/~njas/sequences/ .

[8] N. J. A. Sloane, Classic sequences,

   http://www.research.att.com/~njas/sequences/classic.html .
[9] E. Weisstein, MathWorld, http://mathworld.wolfram.com/ .

2000 Mathematics Subject Classification: Primary 11B37. Keywords: complementary equation, complementary sequences, Fibonacci numbers, golden ratio, Wythoff array, Wythoff sequence.

(Concerned with sequences \underline{A000201}, \underline{A001950}, \underline{A003622}, \underline{A003623}, \underline{A035336}, \underline{A035337}, \underline{A035338}, \underline{A035513}, \underline{A101864}, \underline{A134859}, \underline{A134860}, \underline{A134861}, \underline{A134862}, \underline{A134863}, and \underline{A134864}.)

Received November 27 2007; revised version received July 21 2008. Published in Journal of Integer Sequences, August 3 2008.

Return to Journal of Integer Sequences home page.