Stern–Brocot Tree, Best Approximations, and Continued Fractions

Problem 2: simplest fraction between two given fractions

We continue the Stern–Brocot discussion from Week 2 and focus first on the problem:

We split the problem into two cases:

1. One path is not a continuation of the other.
2. One path is the continuation of the other.

Case 1: one path is not a continuation of the other

Then we use the nearest common ancestor on the Stern–Brocot tree.

So in this example the nearest common ancestor gives the fraction of smallest denominator lying between the two given fractions.

Case 2: one path is the continuation of the other

In this case we use the rule that we may attach an infinite tail without changing the number: one attaches either \(L^{\infty}\) or \(R^{\infty}\) in order to get the longest possible overlap.

First attach the appropriate infinite tail to the shorter path, then do the same to the longer path, and the overlap gives the desired fraction.

Worksheet example

We now return to the Week 2 worksheet problem of finding the simplest fraction between

Using Stern–Brocot paths and the longest overlap, we obtain

hence

Problem 3: best rational approximations

A best approximation to \(\pi\) is a fraction \(\tfrac{p}{q}\) that does a better job than any other fraction \(\tfrac{a}{b}\) with denominator \(b \le q\).

We compare decimal approximations with \(\tfrac{355}{113}\), illustrating that decimal truncation does not necessarily give the best approximation.

Irrational numbers and infinite paths

Every irrational number corresponds to an infinite path on the Stern–Brocot tree that does not end with \(L^{\infty}\) or \(R^{\infty}\).

To find the best approximations, cut the infinite path every time there is a turn.

This raises the next question: how do we find the paths for numbers such as \(\pi\) or \(\tfrac{373}{857}\)? The answer leads to continued fractions.

From decimal expansions to continued fractions

Let's step back to decimal expansion. For example,

Why is base 10 is used at all? We try putting the digits into the denominators instead, producing automatically smaller and smaller pieces. This leads to a nested expression.

Continued fractions

After using parentheses, the expression becomes a continued fraction, written for short in bracket notation.

Continued fractions and the Stern–Brocot tree

For an irrational number, the continued fraction is the sequence of exponents in the Stern–Brocot path.

For example, the continued fraction expansion for \(\pi\) begins with

For rational numbers, there are three equivalent descriptions: adding 1 to the last exponent, attaching \(L^{\infty}\) and ignoring \(R^{\infty}\), or attaching \(R^{\infty}\) and ignoring \(L^{\infty}\).

Examples

We work through examples such as

How to find the continued fraction of a number

Recall quotient and remainder. For example,

Then one inverts the fractional part and repeats the process. Applying this to \(\tfrac{37}{85}\), we derive

The same recursive idea works for irrational numbers as well.