Sequence of Wythoff Pairs contains all Positive Integers exactly Once Each

From ProofWiki
Jump to navigation Jump to search

Theorem

Consider the sequence of Wythoff pairs arranged in sequential order:

$\tuple {0, 0}, \tuple {1, 2}, \tuple {3, 5}, \tuple {4, 7}, \tuple {6, 10}, \tuple {8, 13}, \ldots$


Apart from the first Wythoff pair $\tuple {0, 0}$, every positive integer appears in this sequence exactly once.


Proof

By definition, the $n$th Wythoff pair is $\tuple {\floor {n \phi}, \floor {n \phi^2} }$.

Thus the coordinates of the sequence of Wythoff pairs are the terms of the lower and upper Wythoff sequences.

By definition:

the lower Wythoff sequences is the Beatty sequence on the golden section $\phi$.
the upper Wythoff sequences is the complementary Beatty sequence on the golden section $\phi$.

Also by definition, the complementary Beatty sequence on $x$ is the integer sequence formed by the integers which are missing from $\mathcal B_x$.

Hence the result.

$\blacksquare$


Sources