In mathematics, the Wythoff array is an infinite matrix of integers derived from the Fibonacci sequence and named after Dutch mathematician Willem Abraham Wythoff. Every positive integer occurs exactly once in the array, and every integer sequence defined by the Fibonacci recurrence can be derived by shifting a row of the array.
The Wythoff array was first defined by using Wythoff pairs, the coordinates of winning positions in Wythoff's game. It can also be defined using Fibonacci numbers and Zeckendorf's theorem, or directly from the golden ratio and the recurrence relation defining the Fibonacci numbers.
The Wythoff array has the values
\begin{matrix} 1&2&3&5&8&13&21& … \\ 4&7&11&18&29&47&76& … \\ 6&10&16&26&42&68&110& … \\ 9&15&24&39&63&102&165& … \\ 12&20&32&52&84&136&220& … \\ 14&23&37&60&97&157&254& … \\ 17&28&45&73&118&191&309& … \\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\\ \end{matrix}
Inspired by a similar Stolarsky array previously defined by, defined the Wythoff array as follows. Let
\varphi= | 1+\sqrt{5 |
i
(\lfloori\varphi\rfloor,\lfloori\varphi2\rfloor)
m
i=\lfloorm\varphi\rfloor
Am,n
m
n
Am,1=\left\lfloor\lfloorm\varphi\rfloor\varphi\right\rfloor
Am,2=\left\lfloor\lfloorm\varphi\rfloor\varphi2\right\rfloor
Am,n=Am,n-2+Am,n-1
n>2
The Zeckendorf representation of any positive integer is a representation as a sum of distinct Fibonacci numbers, no two of which are consecutive in the Fibonacci sequence. As describes, the numbers within each row of the array have Zeckendorf representation that differ by a shift operation from each other, and the numbers within each column have Zeckendorf representations that all use the same smallest Fibonacci number. In particular the entry
Am,n
m
(n+1)
Each Wythoff pair occurs exactly once in the Wythoff array, as a consecutive pair of numbers in the same row, with an odd index for the first number and an even index for the second. Because each positive integer occurs in exactly one Wythoff pair, each positive integer occurs exactly once in the array .
Every sequence of positive integers satisfying the Fibonacci recurrence occurs, shifted by at most finitely many positions, in the Wythoff array. In particular, the Fibonacci sequence itself is the first row, and the sequence of Lucas numbers appears in shifted form in the second row .