The diagonal of the Wythoff array

New delights and unexpected connections

The late, great, Bill Thurston once wrote:

William Thurston

“Mathematics has a remarkable beauty, power, and coherence, more than we could have ever expected. It is always changing, as we turn new corners and discover new delights and unexpected connections with old familiar grounds.”

In the hope of capturing a small glimpse of Thurston’s vision of turning new corners and discovering new delights, I want to talk a little about an interesting sequence of whole numbers. So enchanting is this sequence that it holds numerous opportunities for investigation by school students, and challenges for research mathematicians.

The Wythoff array

The sequence I want to discuss comes from the so-called Wythoff array.

This is an infinite array of whole numbers, the beginning of which looks as follows:

The first row might look familiar: it is, apart from a missing “1”, just the sequence of Fibonacci numbers. As we know, the Fibonacci numbers $F_n$ are determined by the recurrence $F_{n+2}=F_{n+1}+F_n$ and the initial conditions for $F_1$ and $F_2$ .

As you can check from the beginning of the array, shown above, the numbers in each row, are, after the first two, just the sum of the two preceding numbers in the row. Each row, in other words, is just a variant of the Fibonacci sequence: what changes is the pair of initial conditions – the first two numbers – in each row.

This infinite array was named after the Dutch mathematician Willem Abraham Wythoff (1865 – 1939), although Wythoff himself did not write down the array: D. R.Morrison, in a 1980 article, “A Stolarsky Array of Wythoff Pairs”, named the array after Wythoff because of Wythoff’s investigations of Wythoff’s game.

The entries in the Wythoff array are easily describable in terms of a recurrence for the entry $A_{m,n}$ in the $m^{th}$ row and $n^{th}$ column:

where $\phi =(1+\sqrt{5})/2$ and where , for a real number $x, \lfloor x\rfloor$ is the floor of $x$ : the greatest integer $\leq x$ .

There is a way to write the entries of the Wythoff array directly in terms of the Fibonacci numbers, detailed in 1994 by Clarke Kimberling:

The Wythoff array has several interesting features, not the least of which is that every positive integer occurs exactly once in exactly one row of the array.

Question: Can you devise a method (an algorithm?) which, given a positive integer $n$ , finds the position $(i,j)$ – the $i^{th}$ row and $j^{th}$ column – of $n$ .

The diagonal elements

We will denote the diagonal entry $A_{n,n}$ of the Wythoff array by $W_n$ . The recurrence for the general entries of the Wythoff array then gives the following formula to calculate the diagonal entries:

The diagonal entries $W_n$ can also be written in terms of a Fibonacci-like recurrence, but with variable coefficients:

where the coefficients $e_n, f_n$ are rational numbers dependent on $n$ .

To see that this possible and to get an explicit formula for $e_n$ and for $f_n$ we simply substitute $W_n =\lfloor n \phi \rfloor F_{n+1} + (n-1)F_n$ into $W_{n+2} = e_nW_{n+1}+f_nW_n$ , use the relation $F_{n+1}=F_{n+1}+F_n$ and equate coefficients of $F_{n+1}$ and $F_n$ .