Consider the following sequence of rational numbers, starting with \( A_ 0 = 0 \) and defined recursively as

\[ A_n = \frac{ 1 } { 2 \lfloor A_{n-1} \rfloor - A_{n-1} + 1 }. \]

Show that every non-negative rational number appears in this sequence exactly once.

The sequence starts off as \( 0 , 1, \frac{1}{2}, 2, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, 3, \frac{1}{4}, \frac { 4}{3}, \ldots \).

## Comments

Sort by:

TopNewestClarification : What is \(R_n\)? – Pratik Shastri · 2 years, 1 month ago

Log in to reply

– Calvin Lin Staff · 2 years, 1 month ago

Ooops, it should have been \(A_n\). Corrected.Log in to reply

numberphile just posted a video on this – Trevor Arashiro · 2 years, 1 month ago

Log in to reply

However, it is not immediately apparent why the above recurrence relation should lead to the Stern-Brocot tree. The relationship between consecutive terms of the Stern-Brocot tree that do not have the same parents is not clear, whereas we have a very simple description in the above recurrence relation.

So yes, one possible way of approach, is to show that the above recurrence relation leads to the Stern-Brocot tree, and hence conclude that it hits each rational number exactly once. – Calvin Lin Staff · 2 years, 1 month ago

Log in to reply