Stern-Brocot tree

If we start with irreducible fractions representing zero andinfinity,

\\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 weobtain

\\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 fractionappears at some iteration and no fraction ever appears twice [1]. The processcan be represented graphically by means of so-calledStern-Brocot tree, named after its discoverers, Moritz Sternand 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.