Smaller Number of Wythoff Pair is Smallest Number not yet in Sequence

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$


The first coordinate of each Wythoff pair is the smallest positive integer which has not yet appeared in the sequence.


Proof

From Sequence of Wythoff Pairs contains all Positive Integers exactly Once Each, every positive integer can be found in the sequence of Wythoff pairs.

From Difference between Terms of Wythoff Pair, the first coordinate is the smaller of the coordinates of the Wythoff pair.

So consider a given Wythoff pair.

Let $p$ be the smallest positive integer which has not yet appeared in the sequence.

It has to appear somewhere.

The terms of both the lower and upper Wythoff sequences are in ascending order.

$n$ must appear in the next Wythoff pair, otherwise a larger positive integer will appear before it when it eventually does appear.

$n$ cannot appear as the second coordinate, or it will be less than whatever number appears as the first coordinate.

Hence $n$ appears as the first coordinate of the next Wythoff pair.

$\blacksquare$


Sources