Stern–Brocot Tree, Best Approximations, and Continued Fractions

Problem 2: simplest fraction between two given fractions

The Week 3 notes continue the Stern–Brocot discussion from Week 2 and focus first on the problem:

The notes 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 the notes use the rule that we may attach an infinite tail without changing the number: one attaches either \(RL^{\infty}\) or \(LR^{\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

The notes return to the Week 2 worksheet problem of finding the simplest fraction between

Using Stern–Brocot paths and the longest overlap, the notes 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\).

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

Irrational numbers and infinite paths

The notes state that 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

The notes step back to decimal expansion. For example,

Then they ask why base 10 is used at all, and suggest 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.

The notes indicate an example for \(\pi\) leading to a beginning such as

For rational numbers, the notes discuss 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

The notes work through examples such as

How to find the continued fraction of a number

The notes recall quotient and remainder. For example,

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

The last page remarks that the same recursive idea works for irrational numbers as well.