Stern-Brocot tree

If we start with irreducible fractions representing zero and infinity,

\frac{0}{1},\frac{1}{0},

and then between adjacent fractions $\frac{m}{n}$ and $\frac{m^{\prime}}{n^{\prime}}$ we insert fraction $\frac{m+m^{\prime}}{n+n^{\prime}}$ , then we obtain

\frac{0}{1},\frac{1}{1},\frac{1}{0}.

Repeating the process, we get

\frac{0}{1},\frac{1}{2},\frac{1}{1},\frac{2}{1},\frac{1}{0},

and then

\frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1},\frac{3}{2},\frac{% 2}{1},\frac{3}{1},\frac{1}{0},

and so forth. It can be proven that every irreducible fraction appears at some iteration and no fraction ever appears twice [1]. The process can be represented graphically by means of so-called Stern-Brocot tree, named after its discoverers, Moritz Stern and Achille Brocot.

\xy*!C\xybox{\xymatrix@C=0.4em{\frac{0}{1}\ar@{.}[d]&&&&&&&&\frac{1}{1}\ar@{-}% [lllld]\ar@{.}[d]\ar@{-}[rrrrd]&&&&&&&&\frac{1}{0}\ar@{.}[d]\\ \frac{0}{1}\ar@{.}[d]&&&&\frac{1}{2}\ar@{-}[lld]\ar@{.}[d]\ar@{-}[rrd]&&&&% \frac{1}{1}\ar@{.}[d]&&&&\frac{2}{1}\ar@{-}[lld]\ar@{.}[d]\ar@{-}[rrd]&&&&% \frac{1}{0}\ar@{.}[d]\\ \frac{0}{1}\ar@{.}[d]&&\frac{1}{3}\ar@{-}[ld]\ar@{.}[d]\ar@{-}[rd]&&\frac{1}{2% }\ar@{.}[d]&&\frac{2}{3}\ar@{-}[ld]\ar@{.}[d]\ar@{-}[rd]&&\frac{1}{1}\ar@{.}[d% ]&&\frac{3}{2}\ar@{-}[ld]\ar@{.}[d]\ar@{-}[rd]&&\frac{2}{1}\ar@{.}[d]&&\frac{3% }{1}\ar@{-}[ld]\ar@{.}[d]\ar@{-}[rd]&&\frac{1}{0}\ar@{.}[d]\\ \frac{0}{1}\ar@{.}+<0em,-5ex>&\frac{1}{4}\ar@{-}+<-0.5em,-5ex>\ar@{.}+<0em,-5% ex>\ar@{-}+<0.5em,-5ex>&\frac{1}{3}\ar@{.}+<0em,-5ex>&\frac{2}{5}\ar@{-}+<-0.5% em,-5ex>\ar@{.}+<0em,-5ex>\ar@{-}+<0.5em,-5ex>&\frac{1}{2}\ar@{.}+<0em,-5ex>&% \frac{3}{5}\ar@{-}+<-0.5em,-5ex>\ar@{.}+<0em,-5ex>\ar@{-}+<0.5em,-5ex>&\frac{2% }{3}\ar@{.}+<0em,-5ex>&\frac{3}{4}\ar@{-}+<-0.5em,-5ex>\ar@{.}+<0em,-5ex>\ar@{% -}+<0.5em,-5ex>&\frac{1}{1}\ar@{.}+<0em,-5ex>&\frac{4}{3}\ar@{-}+<-0.5em,-5ex>% \ar@{.}+<0em,-5ex>\ar@{-}+<0.5em,-5ex>&\frac{3}{2}\ar@{.}+<0em,-5ex>&\frac{5}{% 3}\ar@{-}+<-0.5em,-5ex>\ar@{.}+<0em,-5ex>\ar@{-}+<0.5em,-5ex>&\frac{2}{1}\ar@{% .}+<0em,-5ex>&\frac{5}{2}\ar@{-}+<-0.5em,-5ex>\ar@{.}+<0em,-5ex>\ar@{-}+<0.5em% ,-5ex>&\frac{3}{1}\ar@{.}+<0em,-5ex>&\frac{4}{1}\ar@{-}+<-0.5em,-5ex>\ar@{.}+<% 0em,-5ex>\ar@{-}+<0.5em,-5ex>&\frac{1}{0}\ar@{.}+<0em,-5ex>}}

If we specify position of a fraction in the tree as a path consisting of L(eft) an R(ight) moves along the tree starting from the top (fraction $\frac{1}{1}$ ), and also define matrices

L=\begin{bmatrix}1&1\\ 0&1\end{bmatrix},\qquad R=\begin{bmatrix}1&0\\ 1&1\end{bmatrix},

then product of the matrices corresponding to the path is matrix $\left[\begin{smallmatrix}n&n^{\prime}\\ m&m^{\prime}\end{smallmatrix}\right]$ whose entries are numerators and denominators of parent fractions. For example, the path leading to fraction $\frac{3}{5}$ is LRL. The corresponding matrix product is

LRL=\begin{bmatrix}1&1\\ 0&1\end{bmatrix}\begin{bmatrix}1&0\\ 1&1\end{bmatrix}\begin{bmatrix}1&1\\ 0&1\end{bmatrix}=\begin{bmatrix}2&3\\ 1&2\end{bmatrix},

and the parents of $\frac{3}{5}$ are $\frac{1}{2}$ and $\frac{2}{3}$ .

Continued fractions and Stern-Brocot tree are closely related. A continued fraction $\langle a_{0};a_{1},a_{2},\ldots\rangle$ corresponds to fraction whose path from the top is $R^{a_{0}}L^{a_{1}}R^{a_{2}}\cdots$ with the last element removed. For example,

	$\displaystyle\frac{5}{3}$	$\displaystyle=1+\frac{1}{1+\frac{1}{2}}=\langle 1;1,2\rangle=R^{1}L^{1}R^{2-1}% =RLR,$
	$\displaystyle\frac{4}{11}$	$\displaystyle=0+\frac{1}{2+\frac{1}{1+\frac{1}{3}}}=\langle 0;2,1,3\rangle=R^{% 0}L^{2}R^{1}L^{3-1}=LLRLL.$

The irrational numbers correspond to the infinite paths in the Stern-Brocot tree. For example, the golden mean $\phi=\langle 1;1,1,1,\ldots\rangle$ corresponds to the infinite path $RLRLR\cdots$ . In particular, the denominator of the fraction corresponding to the string $RLR\cdots$ of length $n$ is the $n$ ’th Fibonacci number.

References

1 Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics. Addison-Wesley, 1998. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0836.00001Zbl 0836.00001.

Title	Stern-Brocot tree
\metatable