The Farey Tree (a subset of the Stern-Brocot Tree) begins with the endpoints of 0 and 1 and uses the mediant to find a fraction between each. As with the Farey sequence, this simply involves forming a fraction by adding the two numerators and the two denominators.
The Stern-Brocot Tree begins with the endpoints of 0 (\(\frac{0}{1}\)) and infinity (\(\infty = \frac{1}{0}\)) and uses the mediant to add to the Farey Tree and list all the rationals!
So \(\frac{0}{1}\) and \(\frac{1}{1}\) give \(\frac{0+1}{1+1} = \frac{1}{2}\)
Then \(\frac{0}{1}\) and \(\frac{1}{2}\) give \(\frac{0+1}{1+2} = \frac{1}{3}\) and \(\frac{1}{1}\) and \(\frac{1}{2}\) give \(\frac{1+1}{1+2} = \frac{2}{3}\)
Each subsequent row of fractions is built by continuing this process, stepping either to the left (L) or right (R), beginning from 1. Each \(n\)-th row begins with \(\frac{1}{n}\) and ends with \(\frac{n-1}{n}\).
| \[\frac{0}{1}\] |
\[\frac{1}{0}\] |
| \[\frac{1}{1}\]\[\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\] |
| \[L\]\[\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}\]\[\frac{1+0}{1+1}\]\[\frac{1}{2}\] |
\[R\]\[\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\]\[\frac{1+1}{0+1}\]\[\frac{2}{1}\] |
| \[LL\]\[\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}\]\[\begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}\]\[\frac{1+0}{2+1}\]\[\frac{1}{3}\] |
\[LR\]\[\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\]\[\begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}\]\[\frac{1+1}{1+2}\]\[\frac{2}{3}\] |
\[RL\]\[\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}\]\[\begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}\]\[\frac{2+1}{1+1}\]\[\frac{3}{2}\] |
\[RR\]\[\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\]\[\begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}\]\[\frac{1+2}{0+1}\]\[\frac{3}{1}\] |
From \(\frac{1}{1}\), to get to \(\frac{1}{2}\), move down to the Left (L or 0). To form the continued fraction(s), simply add another 0 or 1 (it does not matter which because both deliver correct but slightly different results). So for \(\frac{1}{2}\), we could add 0 or 1. Begin your continued fraction with zero (or L since all our LEFT (Farey) fractions lie between 0 and 1) and then count each repeated element. Then adding 0 will give the continued fraction \([0, 2]=0+\cfrac{1}{2}\) and adding 1 gives \([0, 1, 1] = 0 + \cfrac{1}{1+\cfrac{1}{1}}\).
In the same way, to get to \(\frac{1}{3}\) from \(\frac{1}{1}\), step LL (or 00). Add another 0 to get (\([0,3]\)) or 1 for (\([0,2,1]\)). For \(\frac{2}{3}\) from \(\frac{1}{1}\), step LR (or 01). Add another 1 to get (\([0,1,1,1]\)) or 0 to get (\([0,1,2]\)).
As shown above, the Farey Tree makes up the left branch of the Stern-Brocot Tree. Each fraction beginning with a RIGHT step will be greater than 1, and complete this amazing tree.
For the right branch of the Stern-Brocot Tree (rationals greater than 1), to get to \(\frac{4}{1}\) from \(\frac{1}{1}\), step RR (or 11). Add another 1 to get (\([3]\)) or 0 for (\([2,1]\)). For \(\frac{8}{5}\) from \(\frac{1}{1}\), step RLRL (or 1010). Add another 1 to get (\([1,1,1,1,1]\)) or 0 to get (\([1,1,1,2]\)).
Observe that any continued fraction ending in 1 can be compacted by adding that trailing one to the previous term.
Try some of your own?
Step by step?
