Extending Stern-Brocot and Continued Fractions

©2022 Compass Learning Technologies ← GXWeb Climbing Around Fraction Trees → Extending Stern-Brocot and Continued Fractions

Extending Stern-Brocot and Continued Fractions

Saltire Software, home of Geometry Expressions and GXWeb

Symbolic computations on this page use Nerdamer Symbolic JavaScript to complement the in-built CAS of GXWeb

I have been fascinated by continued fractions since being first introduced to them by the late Dr Keith Tognetti of the University of Wollongong, almost 4 decades ago. More recently, the work of Dr Bruce Bates (also of Wollongong University) on the Stern-Brocot Continued Fraction has caught my eye and captured my interest.

Here I describe some discoveries I have come across recently which have not only extended my thinking and understanding of Stern-Brocot, but of continued fractions in general, potentially opening new doorways for further exploration.

New to continued fractions?

New to fraction trees? (Press the 'Show more' button)

Every real number, rational and irrational, can be represented by a continued fraction - the rational ones are finite, of course, but both finite and infinite offer some wonderful patterns and opportunities to explore!

Introducing Stern-Brocot

Explore the Magic Table

Building the Fraction Trees

Explore the Calkin-Wilf Tree

Some Matrix Fraction Magic

Continued Fraction Matrices

Tridiagonal Matrices

Matrix as Mediant

A Proposed Alternative Form

Negative (or Reversal) Continued Fractions

Negative Terms in a Continued Fraction

Proof by Mathematical Induction

Mathematical ToolKit

References

Behind the Scenes

Tap the images to climb around and explore the fraction trees

View a short YouTube video on the Stern-Brocot Tree and its Continued Fraction

Introducing Stern-Brocot

The Stern-Brocot Tree is an historically and mathematically significant fraction tree which can potentially serve to list every rational number, with applications to chemistry, cryptography (through its connections with the PaperFold Sequence) and more.

Thanks to Dr Bruce Bates¹ from the University of Wollongong, the Stern-Brocot Tree also has its own continued fraction which can generate every convergent at each level! The focus of our attention here, the Stern-Brocot Continued Fraction offers a surprising and powerful mathematical tool.

An extended form of order 3 is shown below: (tap on blue terms to explore numerical examples)
\[[0,3,1,3,1,5,1,3,1]_{sb}\] \[0 + \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{5 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1}}}}}}}}\]
Convergents ⇒
\[\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}\]

Index

Jump to MathBox

Explore the Magic Table

Introduction: What is a Magic Table?

Introducing the Magic Table: Dimension 1

Explore the Magic Table in 1 Dimension

Introducing the Magic Table: Dimension 2

Explore the Magic Table in 2 Dimensions

Teasing Out the Resultant Continued Fraction

Step by Step

General Continued Fractions: Some Examples

Try More Examples

Try Some Yourself

Introduction: What is a Magic Table?

To convert a real number to a continued fraction is easy! Try this yourself?

But what if you want to go in the other direction? If you have a continued fraction, and would like to know the real number that it represents?

For some rational numbers (and approximations of irrationals), this is (relatively) easy, since the continued fraction is finite. For most, though, it can be quite arduous.

The most commonly used method involves starting from the bottom and working upwards. This approach, however, does not reveal the successive approximations, the convergents, which in many cases may be just as useful as the final result.

\[ \frac{10}{7}\]\[= 1+\frac{3}{7}\]\[= 1 + \frac{1}{\frac{7}{3}}\]\[= 1 + \cfrac{1}{2 + \cfrac{1}{3}} \]\[= [1,2,3]\]

\[ [1,2,3]\]\[= 1 + \cfrac{1}{2 + \cfrac{1}{3}} \]\[= 1 + \frac{1}{\frac{7}{3}}\]\[= 1+\frac{3}{7} \]\[= \frac{10}{7} \]

Alternatively, you might try the Magic Table method!

The magic table¹^,² (first described by Gosper (1972) - credit for the name goes to Associate Professor Terry Gagen of the University of Sydney) offers an efficient and (relatively) simple way to generate the convergents of a continued fraction - it can even be used, in 1 or 2 dimensions, on linear fractional transformations of continued fractions and, in 3 dimensions, forms the basis for Gosper's algorithm for continued fraction arithmetic.

For example, the continued fraction of
\[\sqrt(37) => \]\[a(n) = [6,12,12,12,12,12,12,...]\]\[b(n) = [1,1,1,1,1,1,1...]\] \[6 + \cfrac{1}{12 + \cfrac{1}{12 + \cfrac{1}{12 + \cfrac{1}{12 + \cfrac{1}{12 + \cfrac{1}{12 + \cfrac{1}{12... }}}}}}}\]
Using the approaches described here is much simpler than, for example, matrix methods to calculate a result such as
\[\frac{\sqrt{37} + 4}{7} = \begin{bmatrix} 1 && 4 \\ 0 && 7 \end{bmatrix} \cdot \sqrt(37) = \begin{bmatrix} 1 && 4 \\ 0 && 7 \end{bmatrix} \cdot \begin{bmatrix} \sqrt(37) && 0 \\ 0 && 1 \end{bmatrix} \]
where the linear fractional transformation is the matrix
\[\begin{bmatrix} 1 && 4 \\ 0 && 7 \end{bmatrix} \ and \ \begin{bmatrix} 1 && 0 \\ 0 && 1 \end{bmatrix}\]
represents the identity matrix.

Magic Table Index

Jump to MathBox

\[...\] \[12\] \[12\] \[12\] \[12\] \[12\] \[6\] \[a(n)\]
\[...\] \[1\] \[1\] \[1\] \[1\] \[1\] \[(1)\] \[b(n)\]
\[...\] \[213442\] \[17665\] \[1462\] \[121\] \[10\] \[1\] \[4\]
\[...\] \[148183\] \[12264\] \[1015\] \[84\] \[7\] \[0\] \[7\]

Introducing the Magic Table: Dimension 1

Gosper's original (dimension 1) version of the magic table was presented horizontally, reading from right to left. A simplified form (which delivers each convergent in turn) might be represented as shown above.

Note that Gosper dealt only with simple continued fractions for which all b(n) (numerator) terms may be assumed to be 1. We go a step further here, adding a b(n) row to support general continued fractions.

Can you see how the pairs of numbers below the continued fraction terms are calculated? (Notice that the first convergent is calculated directly from the terms of the linear fractional transformation.)

Tap on these pairs to see, or tap on the red continued fraction terms - from right to left - to see Gosper's Magic Table in action!

Magic Table Index

Jump to MathBox

Introducing the Magic Table: Dimension 2

More importantly, Gosper was not really interested in simply outputting the convergents of continued fractions.

His real goal was to take a continued fraction, operate on it in some way - initially, using a linear fractional transformation, but leading to arithmetic operations with another continued fraction - and output the result directly as a continued fraction: true continued fraction arithmetic!

For this, he needed more dimensions for his magic table!

Teasing Out the Resultant Continued Fraction

It should be noted that drawing out each term of the resultant continued fraction is not always a straightforward operation.

Consider the first TWO convergents of
\[\frac{\sqrt{37} + 4}{7} = \begin{bmatrix} 1 && 4 \\ 0 && 7 \end{bmatrix} \cdot \sqrt(37)\] \[=> \frac{10}{7} \ and \ \frac{121}{84}\]
Taking the floor or integer part of both delivers the same result (\(|\frac{10}{7}| = |\frac{121}{84}| = 1\)), so we can be confident in the first term of our resultant continued fraction.

To continue, we need the dimension 2 table, since we now move one step down and one step to the left (in the table above, or to the right in the table below). The next two convergents to consider are \(\frac{84}{37}\) and \(\frac{1015}{447}\). If the floor values of both agree (which they do in this case), we continue this process, moving down and horizontally forward.

If NOT, then we simply move one step horizontally forward, and try the next pair of convergents, until we find two that agree, and this process gives each subsequent term of our resultant continued fraction.

For a more interesting example, consider Gosper's case of \(e\) with linear fractional transformation, [1,-1,1,1]:
\[tanh(\frac{1}{2}) = \frac{e-1}{e+1}\]
Here we see that the first convergent pair (\(\frac{1}{3}\) and \(\frac{2}{4}\)) both deliver floor values of 0. The second pair (\(\frac{11}{5}\) and \(\frac{4}{2}\)) give us the next resultant term of 2.

Subsequently, though, \(|\frac{5}{1}| = 5\) and \(|\frac{7}{1}| = 7\). We must continue to the next terms, \(\frac{12}{2}\) and (with a little calculation) \(\frac{55}{9}\) (\(4 \cdot 12 + 1 \cdot 7 = 55\) and \(4 \cdot 2 + 1 \cdot 1 = 9\)) to confirm the floor result of 6.

The floor values of pairs of adjacent convergents must differ by no more than 1 to deliver the next term of the resultant continued fraction.

Magic Table Index

Jump to MathBox

For ease of presentation, in our versions, the terms are displayed vertically, with the terms of the linear fractional transformation found at the top of the numerator and denominator columns (rotated -90°).

Magic Table Index

Jump to MathBox

Step by Step

Tap to view:

Simple Convergent Form 1

Simple Convergent Form 2

Gosper Magic Table 1

Gosper Magic Table 2

Gosper Magic Table 3

Gosper Magic Table 4

Gosper Magic Table 5

In its simplest form, Gosper's Magic Table initially offers a convenient way to generate the convergents for a given continued fraction, along with a linear fractional transformation, expressed as a 2x2 matrix.
(Tap for an example) ⇑

Magic Table Index

Jump to MathBox

General Continued Fractions: Some Examples

Note that the Magic Table presented here represents an extension of Gosper's method, supporting general continued fractions in addition to simple ones. For example, did you know that
\[\pi \approx 0 + \cfrac{4}{1 + \cfrac{1}{3 + \cfrac{4}{5 + \cfrac{9}{7 + \cfrac{16}{9 + \cfrac{25}{11 + \cfrac{36}{13 + \cfrac{49}{15 + \cfrac{64}{17 + \cfrac{81}{19...}}}}}}}}}}\]\[a(n) = [0,1,3,5,7,9,11,13,15,17,19]\]\[b(n) = [4,1,4,9,16,25,36,49,64,81]\]

And what about the Farey and Stern-Brocot Continued Fractions: if you wanted to start a list of every rational number, then these amazing continued fractions are perfect for that!

\[0 + \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1}}}} = 0 + \cfrac{1}{3 + \cfrac{1}{-1 + \cfrac{1}{3 + \cfrac{1}{-1}}}}\] \[⇒ [0,\frac{1}{3},\frac{1}{2},\frac{2}{3},1]\]
Farey Sequence Level 3:
mtable([[0,3,-1,3,-1],[1,1,1,1,1]],[1,0,0,1])
OR

mtable([[0,3,1,3,1],[1,-1,-1,-1,-1]],[1,0,0,1])

\[0 + \cfrac{1}{4 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{5 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1}}}}}}}}\] \[⇒ [0,\frac{1}{4}, \frac{1}{3}, \frac{2}{5},\frac{1}{2}, \frac{3}{5}, \frac{3}{4}, \frac{2}{3},1]\]
Farey Sequence Level 4:
mtable([[0,4,-1,3,-1,5,-1,3,-1],[1,1,1,1,1,1,1,1,1]],[1,0,0,1])

OR

mtable([[0,4,1,3,1,5,1,3,1],[1,-1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1])

\[0 + \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{5 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1}}}}}}}}\] \[⇒ [0,\frac{1}{3},\frac{1}{2},\frac{2}{3},1,\frac{3}{2},\frac{2}{1}, \frac{3}{1},\frac{1}{0}]\]
Stern-Brocot Sequence Level 3:
mtable([[0,3,-1,3,-1,5,-1,3,-1],[1,1,1,1,1,1,1,1,1]],[1,0,0,1])

OR

mtable([[0,3,1,3,1,5,1,3],[1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1])

Stern-Brocot Sequence Level 4:
\[0 + \cfrac{1}{4 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{5 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{7 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{5 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1}}}}}}}}}}}}}}}}\] \[⇒ [0,\frac{1}{4}, \frac{1}{3}, \frac{2}{5},\frac{1}{2}, \frac{3}{5}, \frac{3}{4}, \frac{2}{3},1, \frac{3}{2}, \frac{4}{3}, \frac{5}{3},\frac{2}{1}, \frac{5}{2}, \frac{3}{1}, \frac{4}{1}, \frac{1}{0}]\]

mtable([[0,4,-1,3,-1,5,-1,3,-1,7,-1,3,-1,5,-1,3],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]],[1,0,0,1],0,17)

OR

mtable([[0,4,1,3,1,5,1,3,1,7,1,3,1,5,1,3],[1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1],0,17)

Magic Table Index

Jump to MathBox

Try More Examples

Simple (Convergent)
Magic Table
Dimension 1 Gosper
Magic Table
Dimension 2

Enter mtable(), or
mtable(sqrt(37)), or
mtable(sqrt(37),[1,4,0,7]), or even
mtable(sqrt(37),[1,4,0,7],0,12)

Try one of Gosper's examples:
mtable(sqrt(2),[0,2,-1,3],0,12)

You can also enter arrays: mtable([1,2,3,4,5],[1,0,0,1],0,12) or
mtable([[1,2,3,4],[4,3,2,1],[1,0,0,1],0,12)

Try mtable([[2,1,2,3,4,5,6,7,8,9,10],[1,1,2,3,4,5,6,7,8,9,10]],[1,0,0,1],0,12)

Enter gmt(), or
gmt(sqrt(37)), or
gmt(sqrt(37),[1,4,0,7]), or even
gmt(sqrt(37),[1,4,0,7],0,12)

Try one of Gosper's examples:
gmt(sqrt(2),[0,2,-1,3],0,12)

You can also enter arrays: gmt([1,2,3,4,5],[1,0,0,1],0,12) or
gmt([[1,2,3,4],[4,3,2,1],[1,0,0,1],0,12)

Try gmt([[2,1,2,3,4,5,6,7,8,9,10],[1,1,2,3,4,5,6,7,8,9,10]],[1,0,0,1],0,12)

mtable([[0,1,3,5,7,9,11,13,15,17,19],[4,1,4,9,16,25,36,49,64,81,100]],[1,0,0,1],0,12).

Perhaps even compare
mtable([[4,2,2,2,2,2,2,17,294],[-1,-1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1]) with
mtable([[4,-2,2,-2,2,-2,2,-17,294],[1,1,1,1,1,1,1,1,1]],[1,0,0,1])?

Magic Table Index

Index

Jump to MathBox

Building the Fraction Trees

Index

Jump to MathBox

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} ⊕ \frac{1}{0} = \frac{0+1}{1+0} = \frac{1}{1}\]

For the left branch of the Stern-Brocot Tree (the Farey Tree):

\[\frac{0}{1} ⊕ \frac{1}{1} = \frac{0+1}{1+1} = \frac{1}{2}\]

\[Then\ \frac{0}{1} ⊕ \frac{1}{2} = \frac{0+1}{1+2} = \frac{1}{3}\]\[and \ \frac{1}{1} ⊕ \frac{1}{2} = \frac{1+1}{1+2} = \frac{2}{3}\]

For the right branch of the Stern-Brocot Tree:

\[and \ \frac{1}{1} ⊕ \frac{1}{0} = \frac{1+1}{1+0} = \frac{2}{1}\]

\[Then\ \frac{2}{1} ⊕ \frac{1}{1} = \frac{2+1}{1+1} = \frac{3}{2}\]\[and \ \frac{2}{1} ⊕ \frac{1}{0} = \frac{2+1}{1+0} = \frac{3}{1}\]

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}\).

\[\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.

For more detail on building continued fractions from fraction trees, jump to Some Matrix Fraction Magic (section 3).

Try some of your own?

Step by step?

Index

Jump to MathBox

Explore the Calkin-Wilf Tree

Index

Jump to MathBox

The Calkin-Wilf tree (or Tree of All Fractions) is another binary tree which is obtained by starting with the fraction 1/1 and (this time!) adding \(\frac{a}{a+b}\) and \(\frac{a+b}{b}\) iteratively below each fraction \(\frac{a}{b}\).

The Calkin-Wilf Tree was only developed in the year 2000 by Neil Calkin and Herb Wilf (demonstrating that there is still much beautiful and useful mathematics to be discovered), and is also similar to the binary tree of Johannes Kepler (1619) (The image ⇒ shows the Calkin-Wilf rule on the left and Kepler's on the right).

This tree (like the Stern-Brocot tree) generates every rational number. Writing out the terms in a sequence gives

\(\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}\)...

The sequence has the property that each denominator is the next numerator. That means that the nth rational number in the list looks like \(\frac{b(n)}{b(n + 1)}\) (n = 0, 1, 2, . . .), where

{b(n)}_n≥0 = {1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,...}.

This is a bit remarkable - at very least, for its efficiency. This single list can be viewed in (at least) three ways:

As the list of numerators of the Calkin-Wilf Tree,

As the list of denominators of the Calkin-Wilf Tree (after removing the first term) OR

As the actual list of fractions of the Calkin-Wilf Tree by taking each term with its next term!

Differing from the Stern-Brocot tree above, the rationals between 0 and 1 are paired (interleaved) with their reciprocal complements.

Perhaps even simpler than Stern-Brocot, any term of the Calkin-Wilf tree can directly reveal its continued fraction through the binary form of the term number!

Consider the 19th term of the Calkin-Wilf tree: 19 = 10011 (binary) - RLLRR (counting from zero).

For Calkin-Wilf, count repeated terms FROM THE RIGHT to get the continued fraction.

If the binary ends in zero (i.e. if the term is even) then add a zero as the first term - even term values always lie between 0 and 1!

Calkin-Wilf: term 19

=> [2,2,1]

=> \(\frac{7}{3}\)

Explore the binary trees yourself!

Ferreira, J and Mendes, A (2016) A calculational approach to path-based properties of the Eisenstein-Stern and Stern-Brocot trees via matrix algebra

Gobler, Ben (2022) The Calkin-Wilf Tree: Extensions and Applications

Ben Gobler: Listing the Rationals Using Continued Fractions (YouTube)

Index

Jump to MathBox

Some Matrix Fraction Magic

Matrices and Continued Fractions: MathBox entry

Continued fractions can be represented in matrix form, offering some interesting possibilities - and applicable to both simple and generalised continued fractions.

Three distinct variants are offered here.

1. Continued Fraction Matrices

The most-commonly documented approach⁷ involves the product of 2 x 2 matrices.
\[a_0+\cfrac{b_0}{a_1 + \cfrac{b_1}{a_2 + \cfrac{b_2}{a_3 + \cfrac{b_3}{a_4...}}}} = \]\[\begin{bmatrix} a_0 & b_0 \\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} a_1 & b_1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_2 & b_2 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_3 & b_3 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_4 & 1 \\ 1 & 0 \end{bmatrix}... \]

For example, arithmetic operations can be readily expressed.
\[ [1,2,3,1,2,3,1,2,3,1...] =>\]\[1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{1...}}}}}}\]\[\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ...\] \[ x = 1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{x}}} \]\[= \frac{4+\sqrt(37)}{7} \] \[If... \sqrt{37}= 6+ \cfrac{1}{12+\cfrac{1}{12+\cfrac{1}{12+\cfrac{1}{12+...}}}}\]\[=> \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} ... \] \[Then... \frac{4+\sqrt(37)}{7} = \begin{bmatrix} 1 & 4 \\ 0 & 7 \\ \end{bmatrix} \cdot \sqrt{37} \]\[ => \begin{bmatrix} 1 & 4 \\ 0 & 7 \\ \end{bmatrix} \cdot \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} ... \]
Even less predictable ones:
\[ [2,2,3,1,1,2,3,1,1,2,3...] =>\]\[2 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{3...}}}}}}\] \[ \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} ... \] \[ x-1 = 1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{x-1}}}} \]\[ x-1 = 1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{x-1}{x}}} \]\[= \frac{4+\sqrt(11)}{3} \] \[If...\sqrt{11}= 3+ \cfrac{1}{3+\cfrac{1}{6+\cfrac{1}{3+\cfrac{1}{6+...}}}}\]\[=> \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} ... \] \[Then... \frac{4+\sqrt(11)}{3} = \begin{bmatrix} 1 & 4 \\ 0 & 3 \\ \end{bmatrix} \cdot \sqrt{11} \]\[ => \begin{bmatrix} 1 & 4 \\ 0 & 3 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} ... \]

Index

Jump to MathBox

2. Tridiagonal Matrix Continued Fractions

Two alternative approaches involve larger square (tridiagonal) matrices. (eg Frommer, Kahl and Tsolakis (2021) and Qi, Wen Guo and Lim (2020))
\[Let \ M = \begin{bmatrix} a_0 & b_0 & 0 & 0 & 0 \\ -1 & a_1 & b_1 & 0 & 0 \\ 0 & -1 & a_2 & b_2 & 0 \\ 0 & 0 & -1 & a_3 & b_3 \\ 0 & 0 & 0 & -1 & a_4\end{bmatrix}\]
Then taking the inverse of M, the first ([1,1]) term gives the reciprocal of the final convergent of the continued fraction:
\[\frac{1}{inv(M)[1,1]} = a_0+\cfrac{b_0}{a_1 + \cfrac{b_1}{a_2 + \cfrac{b_2}{a_3 + \cfrac{b_3}{a_4}}}}\]
A second approach involves the determinants of two square matrices, p and q as follows:

\[p = \begin{bmatrix} a_0 & b_0 & 0 & 0 & 0 \\ -1 & a_1 & b_1 & 0 & 0 \\ 0 & -1 & a_2 & b_2 & 0 \\ 0 & 0 & -1 & a_3 & b_3 \\ 0 & 0 & 0 & -1 & a_4\end{bmatrix}\] \[q = \begin{bmatrix} a_1 & b_1 & 0 & 0 \\ -1 & a_2 & b_2 & 0 \\ 0 & -1 & a_3 & b_3 \\ 0 & 0 & -1 & a_4\end{bmatrix}\]
\[a_0+\cfrac{b_0}{a_1 + \cfrac{b_1}{a_2 + \cfrac{b_2}{a_3 + \cfrac{b_3}{a_4}}}} = \frac{det(p)}{det(q)}\]

Index

Mathematical ToolBox

Some expected relationships...

\[1+\cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{4}}}= \]\[f(x) = \begin{bmatrix} 1 & 1 & 0 & 0 \\ -1 & 2 & 1 & 0 \\ 0 & -1 & 3 & 1 \\ 0 & 0 & -1 & 4 \end{bmatrix}\]\[g(x) = inv(\begin{bmatrix} 1 & 1 & 0 & 0 \\ -1 & 2 & 1 & 0 \\ 0 & -1 & 3 & 1 \\ 0 & 0 & -1 & 4 \end{bmatrix})\]\[=\frac{1}{43} \begin{bmatrix} 30 & -13 & 4 & -1 \\ 13 & 13 & -4 & 1 \\ 4 & 4 & 12 & -3 \\ 1 & 1 & 3 & 10 \end{bmatrix}\]\[g(x)\cdot f(x) =\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\]

And even some unexpected ones!

\[[1,2,3,4,5]= \]\[1+\cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{5}}}}= \frac{225}{157}\]\[\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 4 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 5 & 1 \\ 1 & 0 \end{bmatrix} \]\[= \begin{bmatrix} 225 & 43 \\ 157 & 30 \end{bmatrix}\] \[det(\begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ -1 & 2 & 1 & 0 & 0 \\ 0 & -1 & 3 & 1 & 0 \\ 0 & 0 & -1 & 4 & 1 \\ 0 & 0 & 0 & -1 & 5\end{bmatrix}) = 225\]\[det(\begin{bmatrix} 2 & 1 & 0 & 0 \\ -1 & 3 & 1 & 0 \\ 0 & -1 & 4 & 1 \\ 0 & 0 & -1 & 5\end{bmatrix})=157\]

Tap on the matrix examples above and follow the directions. Then just press \(h\) (at the end, you may need to press the TextBoxes button to lay out the result correctly).

3. Matrix as Mediant: Building the Stern-Brocot and Calkin-Wilf Trees

Returning to 2 x 2 matrices, we find another surprisingly simple and powerful matrix approach to building BOTH the Stern-Brocot^8,9 AND Calkin-Wilf Trees^10,11,12, and consequently, listing all possible rationals.

We begin by viewing 2 x 2 matrices in a new way, as defining the mediant:
\[\begin{bmatrix} a & b \\ c & d \end{bmatrix} => \frac{a}{c} ⊕ \frac{b}{d} = \frac{a+b}{c+d}\]
Then the familiar identity matrix becomes
\[\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} =>\frac{1}{0} ⊕ \frac{0}{1} = \frac{1+0}{0+1} = \frac{1}{1}\]
Now we define two matrices, which will serve as left (L) and right (R) steps for our tree:
\[L = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} => \frac{1}{2} \]\[ and \ R = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} => \frac{2}{1} \]
Then any term \(\frac{a+c}{b+d}\) of our Stern-Brocot Tree can be represented by a matrix
\[M = \begin{bmatrix} a & b \\ c & d \end{bmatrix} => \frac{a+c}{b+d}\]
with parents \(\frac{a}{c}\) and \(\frac{b}{d}\) and determinant 1. Such a matrix can serve as the parent for two further matrices:

\[M \cdot L = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \] \[M\cdot L = \begin{bmatrix} a+b & b \\ c+d & d \end{bmatrix} \] \[M\cdot L => \frac{a+2\cdot b}{c+2\cdot d} \] \[ M \cdot R = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\] \[ M\cdot R = \begin{bmatrix} a & a+b \\ c & c+d \end{bmatrix}\] \[ M\cdot R => \frac{2\cdot a+ b}{2\cdot c+ d}\]

Further, the same matrix, resulting from the repeated product of L and R matrices as described above, delivers the corresponding Calkin-Wilf term \(\frac{b}{a}\)!
\[M = \begin{bmatrix} a & b \\ c & d \end{bmatrix} => \frac{b}{a}\]

Index

Mathematical ToolBox

Beginning with our identity matrix
\[M = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} => \frac{1+0}{0+1} = \frac{1}{1}\]
Notice the parents of \(\frac{1}{1}\) are \(\frac{0}{1}\) and \(\frac{1}{0}\)?

We quickly see the effects of a Left and Right step:

\[M \cdot L = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \] \[M\cdot L = \begin{bmatrix} 1+0 & 0+0 \\ 0+1 & 0+1 \end{bmatrix} \] \[M\cdot L = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \] \[M\cdot L => \frac{1+0}{1+1} \] \[M\cdot L => \frac{1}{2} \] \[M \cdot R = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\] \[M\cdot R = \begin{bmatrix} 1+0 & 1+0 \\ 0+0 & 0+1 \end{bmatrix}\] \[M\cdot R = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} *\] \[M\cdot R => \frac{1+ 1}{0+ 1}\] \[M\cdot R => \frac{2}{1}\]

Line * shows that the Stern-Brocot parents of \(\frac{1}{2}\) are \(\frac{0}{1}\) and \(\frac{1}{1}\) and the SB parents of \(\frac{2}{1}\) are \(\frac{1}{1}\) and \(\frac{1}{0}\)?

Then, for example, RLRR =>

\(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\) \(\cdot\) \( \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\) \(\cdot\) \( \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\)
\[= \begin{bmatrix} 2 & 5 \\ 1 & 3 \end{bmatrix}\]\[= \frac{7}{4} (SB) \ and \ \frac{5}{2} (CW)\]

Refer now to the section Building the Fraction Trees to see this process in more detail, and try some for yourself!

Index

Jump to MathBox

A Proposed Alternative Form

Index

Jump to MathBox

Complementing the form above described by Bates (2014), an alternate form is proposed: an equivalent "simple" continued fraction form for which the repeated unary values are negated:
\[[0,3,-1,3,-1,5,-1,3,-1]\] \[= 0 + \cfrac{1}{3 + \cfrac{1}{-1 + \cfrac{1}{3 + \cfrac{1}{-1 + \cfrac{1}{5 + \cfrac{1}{-1 + \cfrac{1}{3 + \cfrac{1}{-1}}}}}}}}\]
Index

Jump to MathBox

While the simple continued fraction form generally consists only of positive non-zero terms, negative terms can be used and are well-documented. ^2,3,4

The motivation for this alternate form is twofold:

mathematical curiosity upon discovery of what appears to be a general rule for simplification of a particular type of general continued fraction, and

one of computational convenience for computer-aided calculation of continued fractions, like that accompanying this page. A simple continued fraction can be readily entered as a single list of terms, such as
\[[0,3,-1,3,-1,5,-1,3,-1]\]
rather than the usual more involved forms:
\[0 + \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{5 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1}}}}}}}}\] \[= 0 + \cfrac{1}{3 + \cfrac{1}{-1 + \cfrac{1}{3 + \cfrac{1}{-1 + \cfrac{1}{5 + \cfrac{1}{-1 + \cfrac{1}{3 + \cfrac{1}{-1}}}}}}}}\]

Index

Jump to MathBox

Negative (or Reversal) Continued Fractions

Index

Jump to MathBox

Before considering negative terms within continued fractions, a note about the continued fractions of negative numbers.
\[\frac{10}{7} = [1,2,3] = 1+\cfrac{1}{2+\cfrac{1}{3}}\]
Begin by observing that
\[-\frac{10}{7} \neq -1-\cfrac{1}{-2-\cfrac{1}{-3}} (= -\frac{2}{5})\]
AND
\[-\frac{10}{7} \neq 1-\cfrac{1}{2-\cfrac{1}{3}} (= \frac{2}{5})\]
However
\[-\frac{10}{7} = [-1,-2,-3] = -1+\cfrac{1}{-2+\cfrac{1}{-3}}\]
and (perhaps surprisingly?)
\[\frac{10}{7} = [2,2,4]^- = 2-\cfrac{1}{2-\cfrac{1}{4}}\]

Did you know that there are TWO classical forms for continued fractions? I only found this out recently.

The simple or general form is built by taking the floor (or whole number part) of the fraction at each level and adding the reciprocal of the tail.

To convert a real number (n) to a continued fraction is easy!

Index

Jump to MathBox

The reversal or negative form takes instead the ceiling or next whole number value above, and subtracts the value of the term to form the tail! The reciprocal of this tail then forms the next term in the process.

To convert a real number (n) to a negative or reversal continued fraction is just as easy!

Try this yourself?

Step 1: Take the integer part of the number - floor[n] or Math.floor(n): This is your first index (call it \(a_0 \)), and first convergent.

Step 2: Subtract the integer part to leave the decimal part - the tail. \( Tail = n - floor(n) \)

Step 3: Calculate the reciprocal of the tail (\( 1 \over Tail \)) - this should give a number greater than or equal to 1.

Step 4: Take the integer part of this reciprocal value (\(a_1 = floor({ 1 \over Tail }) \)): This is your next index - call it \(a_1 \), and \({a_0 + {1 \over a_1}} \) the next convergent.

Step 5: Return to Step 2 and repeat the process...

Try this yourself?

Step 1: Round up to the integer above the number - ceil[n] or Math.ceil(n): This is your first index (call it \(a_0 \)), and first convergent.

Step 2: Subtract the current value from the integer part to leave the decimal part - the tail. \( Tail = ceil(n) - n \)

Step 3: Calculate the reciprocal of the tail (\( 1 \over Tail \)) - this should give a number greater than or equal to 1.

Step 4: Take the ceiling of this reciprocal value (\(a_1 = ceil({ 1 \over Tail }) \)): This is your next index - call it \(a_1 \), and \({a_0 + {1 \over a_1}} \) the next convergent.

Step 5: Return to Step 2 and repeat the process...

\[\frac{10}{7} = [1,2,2,1] \]\[= 1 + \cfrac{1}{2 + \cfrac{1}{2+\cfrac{1}{1}}}\]
(Enter 10/7 or 1,2,3 or 1,2,2,1)
\[[\frac{10}{7}]^{-} = [2,2,4]^{-} \]\[= 2 - \cfrac{1}{2 - \cfrac{1}{4}}\]
(Enter [10/7]^- or [2,2,4]^-
or [10/7]{neg} or [2,2,4]{neg})

\[\frac{43}{30} = [1,2,3,4] \]\[= 1 + \cfrac{1}{2 + \cfrac{1}{3+\cfrac{1}{4}}}\]
(Enter 43/30 or 1,2,3,4)
\[[\frac{43}{30}]^{-} = [2,2,5,2,2,2]^{-} \]\[= 2 - \cfrac{1}{2 - \cfrac{1}{5-\cfrac{1}{2-\cfrac{1}{2-\cfrac{1}{2}}}}}\]
(Enter [43/30]^- or [2,2,5,2,2,2]^-
or [43/30]{neg} or [2,2,5,2,2,2]{neg})

Try a few more examples and see if you can see a pattern...

HINT: It helps if your simple continued fraction form has an EVEN number of terms!

Index

Converting to the Negative Form

With thanks to Morier-Genoud and Ovsienko (2019)⁵

Let \(r\) and \(s\) be two coprime positive integers, and assume that \(r > s\). The rational number \(\frac{r}{s}\) has unique expansions
\[\frac{r}{s} = a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3+\cfrac{1}{...a_{2m}}}}\] \[= c_1 - \cfrac{1}{c_2 - \cfrac{1}{c_3-\cfrac{1}{...c_k}}}\]
where \(a_i \geq 1\) and \(c_i \geq 2\) for all \(i\). The first is called a simple continued fraction and the second, a negative or reversal continued fraction.

Note that we can always assume a simple continued fraction has an even number of terms since every such continued fraction can be expressed in both a compact form (with last term not equal to 1) and an expanded form:
\[[a_1, a_2,..., a_n] = [a_1, a_2,..., a_{n}-1, 1]\]
Then the terms of a negative or reversal continued fraction may be derived from those of the equivalent simple form as follows:
\[[c_1, c_2, c_3,..., c_{k-1}, c_k] = \] \[[a_1+1, 2 \ (repeated \ a_2-1\ times)..., \]\[a_3+2, 2 \ (repeated \ a_4-1\ times)..., \]\[a_{2n-1}+2, 2 \ (repeated\ a_{2n} \ times)]\]

Index

Jump to MathBox

Negative Terms in a Continued Fraction

Index

Jump to MathBox

As noted by Knott², LaGrange points out that it is a simple matter of algebra to show that we can remove subtractions in favour of addtions.

Wherever there is a subtraction, "push" it into the rest of the CF making positive numbers into negatives. We use C to represent the rest of a CF which may be empty or consist of one or more terms:
\[a - \frac{1}{b+C} = a + \frac{-1}{b+C} = a + \frac{1}{-b-C}\]
Then if
\[C = \frac{1}{c+\frac{1}{d + \frac{1}{e+...}}}\]
note that a negative value in a numerator ONLY changes the signs of the subsequent pair of numerator and denominator - this then flows on through the remaining terms to deliver an equal result without requiring any further sign changes.
\[a - \frac{1}{b+\frac{1}{c+\frac{1}{d + \frac{1}{e+...}}}}\] \[ = a + \frac{-1}{b+\frac{1}{c+\frac{1}{d + \frac{1}{e+...}}}}\] \[ = a + \frac{1}{-b-\frac{1}{c+\frac{1}{d + \frac{1}{e+...}}}}\]
Observe from the linked example that this holds for any occurrence within the terms of the continued fraction.

And for a pair of consecutive negative numerators?
\[a + \frac{1}{b-\frac{1}{c-\frac{1}{d + \frac{1}{e+...}}}}\] \[ = a + \frac{1}{b+\frac{-1}{c+\frac{-1}{d + \frac{1}{e+...}}}}\] \[= a + \frac{1}{b+\frac{1}{-c+\frac{1}{d + \frac{1}{e+...}}}}\]
Simpler still!

Each consecutive pair of negative numerator values results in just a single negative leading term (denominator) in the second level. All other negative values cancel.

A string of sequential negative numerators, then, will result in alternating positive and negative leading terms, as proposed.

Index

Jump to MathBox

The question: \[Is\ [0,3,1,3,1,5,1,3]_{sb} = [0,3,-1,3,-1,5,-1,3]?\]
\[Is\ 0 + \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{3 - \cfrac{1}{1 - \cfrac{1}{5 - \cfrac{1}{1 - \cfrac{1}{3}}}}}}}\] \[= 0+\cfrac{1}{3+\cfrac{1}{-1+\cfrac{1}{3+\cfrac{1}{-1+\cfrac{1}{5+\cfrac{1}{-1+\cfrac{1}{3}}}}}}}\]
The answer to the specific case may be readily verified by tapping on the blue text above, and then tapping, in turn, upon the \(f\), \(g\) and \(h\) buttons provided.

The interested reader is then invited to try other values and ascertain experimentally that the two given forms are equivalent in their output.

In general terms, \[Is\ [a_{0}, a_{1}, 1, a_{2}, 1, a_{3},1...]_{sb} = [a_{0}, a_{1}, -1, a_{2}, -1, a_{3},-1...]?\]
\[Is \ a_{0}+\cfrac{1}{a_{1}-\cfrac{1}{1-\cfrac{1}{a_{2}-\cfrac{1}{1-\cfrac{1}{a_{3}-\cfrac{1}{1...}}}}}}\]\[= a_{0}+\cfrac{1}{a_{1}+\cfrac{1}{-1+\cfrac{1}{a_{2}+\cfrac{1}{-1+\cfrac{1}{a_{3}+\cfrac{1}{-1...}}}}}}\]
The answer to the more general case may be attained through a simple inductive proof.

Index

Jump to MathBox

Proof by Mathematical Induction

Index

Jump to MathBox

We prove the following equivalence results (Bates, 2022)

Theorem 1 (Equivalent Continued Fractions)

Let
\[K_{2n} = \cfrac{a_{1}}{b_{1}-\cfrac{a_{2}}{b_{2}-\cfrac{a_{3}}{b_{3}-\cfrac{a_{4}}{b_{4} - \cdots -\cfrac{a_{2n-1}}{b_{2n-1} - \cfrac{a_{2n}}{b_{2n}}}}}}}\]

\[= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2} & b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{4} & b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} -a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2n} & b_{2n} \\ 1 & 0 \end{bmatrix} \]

and
\[K'_{2n} = \cfrac{a_{1}}{b_{1} + \cfrac{a_{2}}{-b_{2}+\cfrac{a_{3}}{b_{3}+\cfrac{a_{4}}{-b_{4} + \cdots +\cfrac{a_{2n-1}}{b_{2n-1} + \cfrac{a_{2n}}{-b_{2n}}}}}}}\]

\[= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2} & -b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{4} & -b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2n} & -b_{2n} \\ 1 & 0 \end{bmatrix} \]

Then
\[K_{n} = K'_{n}\]
Index

Jump to MathBox

Proof: We prove the result by induction. We have:

\[K_1 = K'_1 = \frac{a_1}{b_1} \ and\]

\[K_2 = K'_2 = \frac{a_1 b_2}{b_1 b_2 - a_2}\]

There are two cases to consider:

(i) Suppose \(K_{2n} = K'_{2n}\). That is
\[\cfrac{a_{1}}{b_{1}-\cfrac{a_{2}}{b_{2}-\cfrac{a_{3}}{b_{3}-\cfrac{a_{4}}{b_{4} - \cdots -\cfrac{a_{2n-1}}{b_{2n-1} - \cfrac{a_{2n}}{b_{2n}}}}}}}\]\[= \cfrac{a_{1}}{b_{1} + \cfrac{a_{2}}{-b_{2}+\cfrac{a_{3}}{b_{3}+\cfrac{a_{4}}{-b_{4} + \cdots +\cfrac{a_{2n-1}}{b_{2n-1} + \cfrac{a_{2n}}{-b_{2n}}}}}}}\]

\[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2} & b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{4} & b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} -a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2n} & b_{2n} \\ 1 & 0 \end{bmatrix} \] \[= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2} & -b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{4} & -b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2n} & -b_{2n} \\ 1 & 0 \end{bmatrix} \]

Then
\[\cfrac{a_{1}}{b_{1}-\cfrac{a_{2}}{b_{2}-\cfrac{a_{3}}{b_{3}-\cfrac{a_{4}}{b_{4} - \cdots -\cfrac{a_{2n-1}}{b_{2n-1} - \cfrac{a_{2n}}{b_{2n} - \cfrac{a_{2n+1}}{b_{2n+1}}}}}}}}\]\[= \cfrac{a_{1}}{b_{1}-\cfrac{a_{2}}{b_{2}-\cfrac{a_{3}}{b_{3}-\cfrac{a_{4}}{b_{4} - \cdots -\cfrac{a_{2n-1}}{b_{2n-1} - \cfrac{a_{2n} b_{2n+1}}{b_{2n} b_{2n+1} - a_{2n+1}}}}}}} \ (1)\]

\[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2} & b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{4} & b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} -a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2n} & b_{2n} \\ 1 & 0 \end{bmatrix} \begin{bmatrix} -a_{2n+1} & b_{2n+1} \\ 1 & 0 \end{bmatrix} \] \[= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2} & b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{4} & b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} -a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2n} b_{2n+1} & b_{2n} b_{2n+1} - a_{2n+1} \\ 1 & 0 \end{bmatrix} \ (1)\]

and
\[\cfrac{a_{1}}{b_{1} + \cfrac{a_{2}}{-b_{2}+\cfrac{a_{3}}{b_{3}+\cfrac{a_{4}}{-b_{4} + \cdots +\cfrac{a_{2n-1}}{b_{2n-1} + \cfrac{a_{2n}}{-b_{2n} + \cfrac{a_{2n+1}}{-b_{2n+1}}}}}}}}\]\[= \cfrac{a_{1}}{b_{1} + \cfrac{a_{2}}{-b_{2}+\cfrac{a_{3}}{b_{3}+\cfrac{a_{4}}{-b_{4} + \cdots +\cfrac{a_{2n-1}}{b_{2n-1} + \cfrac{a_{2n} b_{2n+1}}{-(b_{2n} b_{2n+1} - a_{2n+1}})}}}}} \ (2)\]

\[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2} & -b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{4} & -b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2n} & -b_{2n} \\ 1 & 0 \end{bmatrix} \begin{bmatrix} -a_{2n+1} & b_{2n+1} \\ 1 & 0 \end{bmatrix} \] \[= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2} & -b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{4} & -b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2n} a_{2n+1} & -(b_{2n} b_{2n+1} - a_{2n+1}) \\ 1 & 0 \end{bmatrix} \ (2)\]

By our induction hypothesis, (1) and (2) are identical - we have simply replaced \(\frac{a_{2n}}{b_{2n}}\) with \(\frac{a_{2n} b_{2n+1}}{b_{2n} b_{2n+1} - a_{2n+1}}\).
\[Thus \ K_{2n+1} = K'_{2n+1}\]

Index

Jump to MathBox

(ii) From (i), \(\ K_{2n+1} = K'_{2n+1}\). That is
\[\cfrac{a_{1}}{b_{1}-\cfrac{a_{2}}{b_{2}-\cfrac{a_{3}}{b_{3}-\cfrac{a_{4}}{b_{4} - \cdots -\cfrac{a_{2n-1}}{b_{2n-1} - \cfrac{a_{2n}}{b_{2n}}}}}}}\]\[= \cfrac{a_{1}}{b_{1} + \cfrac{a_{2}}{-b_{2}+\cfrac{a_{3}}{b_{3}+\cfrac{a_{4}}{-b_{4} + \cdots +\cfrac{a_{2n-1}}{b_{2n-1} + \cfrac{a_{2n}}{-b_{2n}}}}}}}\]

\[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2} & b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{4} & b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} -a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2n} & b_{2n} \\ 1 & 0 \end{bmatrix} \] \[= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2} & -b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{4} & -b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2n} & -b_{2n} \\ 1 & 0 \end{bmatrix} \]

Then
\[\cfrac{a_{1}}{b_{1}-\cfrac{a_{2}}{b_{2}-\cfrac{a_{3}}{b_{3}-\cfrac{a_{4}}{b_{4} - \cdots -\cfrac{a_{2n-1}}{b_{2n-1} - \cfrac{a_{2n}}{b_{2n} - \cfrac{a_{2n+1}}{b_{2n+1}}}}}}}}\]\[= \cfrac{a_{1}}{b_{1}-\cfrac{a_{2}}{b_{2}-\cfrac{a_{3}}{b_{3}-\cfrac{a_{4}}{b_{4} - \cdots -\cfrac{a_{2n-1}}{b_{2n-1} - \cfrac{a_{2n} b_{2n+1}}{b_{2n} b_{2n+1} - a_{2n+1}}}}}}} \ (3)\]

\[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2} & b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{4} & b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} -a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2n} & b_{2n} \\ 1 & 0 \end{bmatrix} \begin{bmatrix} -a_{2n+1} & b_{2n+1} \\ 1 & 0 \end{bmatrix} \] \[= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2} & b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{4} & b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} -a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} -a_{2n} b_{2n+1} & b_{2n} b_{2n+1} - a_{2n+1} \\ 1 & 0 \end{bmatrix} \ (3)\]

and
\[\cfrac{a_{1}}{b_{1} + \cfrac{a_{2}}{-b_{2}+\cfrac{a_{3}}{b_{3}+\cfrac{a_{4}}{-b_{4} + \cdots +\cfrac{a_{2n-1}}{b_{2n-1} + \cfrac{a_{2n}}{-b_{2n} + \cfrac{a_{2n+1}}{-b_{2n+1}}}}}}}}\]\[= \cfrac{a_{1}}{b_{1} + \cfrac{a_{2}}{-b_{2}+\cfrac{a_{3}}{b_{3}+\cfrac{a_{4}}{-b_{4} + \cdots +\cfrac{a_{2n-1}}{b_{2n-1} + \cfrac{a_{2n} b_{2n+1}}{-(b_{2n} b_{2n+1} - a_{2n+1}})}}}}} \ (4)\]

\[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2} & -b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{4} & -b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2n} & -b_{2n} \\ 1 & 0 \end{bmatrix} \begin{bmatrix} -a_{2n+1} & b_{2n+1} \\ 1 & 0 \end{bmatrix} \] \[= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2} & -b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{4} & -b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} a_{2n-1} & b_{2n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2n} a_{2n+1} & -(b_{2n} b_{2n+1} - a_{2n+1}) \\ 1 & 0 \end{bmatrix} \ (4)\]

By our induction hypothesis, (3) and (4) are identical - we have simply replaced \(\frac{a_{2n+1}}{b_{2n+1}}\) with \(\frac{a_{2n+1} b_{2n+2}}{b_{2n+1} b_{2n+2} - a_{2n+2}}\).
\[Thus \ K_{2n+2} = K'_{2n+2}\]
and so our result is true for all \(n\).

Index

Jump to MathBox

Theorem 2 (Equivalence transformations of Continued Fractions)

We can extend further the different possible continued fractions that each can represent the Stern-Brocot continued fraction. We first prove a result by Wall⁶.

If \(c \neq 0\) then for
\[K_{n} = b_0 + \cfrac{a_{1}}{b_{1} + \cfrac{a_{2}}{b_{2} + \cfrac{a_{3}}{b_{3} + \cfrac{a_{4}}{b_{4} + \cdots + \cfrac{a_{n-1}}{b_{n-1} + \cfrac{a_{n}}{b_{n}}}}}}}\]

\[= \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2} & b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{4} & b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} a_{n-1} & b_{n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{n} & b_{n} \\ 1 & 0 \end{bmatrix} \]

and
\[K'_{n} = a_0 + \cfrac{c_{1} a_{1}}{c_{1} b_{1} + \cfrac{c_{1} c_{2} a_{2}}{c_{2} b_{2}+\cfrac{c_{2} c_{3} a_{3}}{c_{3} b_{3}+\cfrac{c_{3} c_{4} a_{4}}{c_{4} b_{4} + \cdots +\cfrac{c_{n-2} c_{n-1} a_{n-1}}{c_{n-1} b_{n-1} + \cfrac{c_{n-1} c_{n} a_{n}}{c_{n} b_{n}}}}}}}\]

\[= \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{1} a_{1} & c_{1} b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{1} c_{2} a_{2} & c_{2} b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{2} c_{3} a_{3} & c_{3} b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{3} c_{4} a_{4} & c_{4} b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} c_{n-2} c_{n-1} a_{n-1} & c_{n-1} b_{n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{n-1} c_{n} a_{n} & c_{n} b_{n} \\ 1 & 0 \end{bmatrix} \]

then
\[K_{n} = K'_{n}\]
Index

Jump to MathBox

Proof: We prove the result by induction. We have:

\[K_0 = K'_0 = b_0 \ and\]

\[K_1 = K'_1 = \frac{a_1}{b_1}\]

Suppose our result is true for some \(n\). Then
\[K_{n+1} = b_0 + \cfrac{a_{1}}{b_{1} + \cfrac{a_{2}}{b_{2} + \cfrac{a_{3}}{b_{3} + \cfrac{a_{4}}{b_{4} + \cdots + \cfrac{a_{n-1}}{b_{n-1} + \cfrac{a_{n}}{b_{n} + \cfrac{a_{n+1}}{b_{n+1}}}}}}}}\] \[= b_0 + \cfrac{a_{1}}{b_{1} + \cfrac{a_{2}}{b_{2} + \cfrac{a_{3}}{b_{3} + \cfrac{a_{4}}{b_{4} + \cdots + \cfrac{a_{n-1}}{b_{n-1} + \cfrac{a_{n} b_{n+1}}{b_{n} b_{n+1} + a_{n+1}}}}}}}\]

\[= \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2} & b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{4} & b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} a_{n-1} & b_{n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{n} & b_{n} \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_{n+1} & b_{n+1} \\ 1 & 0 \end{bmatrix} \] \[= \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{1} & b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{2} & b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{3} & b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{4} & b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} a_{n-1} & b_{n-1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{n} b_{n+1} & b_{n} b_{n+1} + a_{n+1} \\ 1 & 0 \end{bmatrix} \]

and
\[K'_{n} = a_0 + \cfrac{c_{1} a_{1}}{c_{1} b_{1} + \cfrac{c_{1} c_{2} a_{2}}{c_{2} b_{2}+\cfrac{c_{2} c_{3} a_{3}}{c_{3} b_{3}+\cfrac{c_{3} c_{4} a_{4}}{c_{4} b_{4} + \cdots +\cfrac{c_{n-2} c_{n-1} a_{n-1}}{c_{n-1} b_{n-1} + \cfrac{c_{n-1} c_{n} a_{n}}{c_{n} b_{n}}}}}}}\] \[K'_{n+1} = a_0 + \cfrac{c_{1} a_{1}}{c_{1} b_{1} + \cfrac{c_{1} c_{2} a_{2}}{c_{2} b_{2}+\cfrac{c_{2} c_{3} a_{3}}{c_{3} b_{3}+\cfrac{c_{3} c_{4} a_{4}}{c_{4} b_{4} + \cdots +\cfrac{c_{n-1} c_{n} a_{n}}{c_{n} b_{n} + \cfrac{c_{n} c_{n+1} a_{n+1}}{c_{n+1} b_{n+1}}}}}}}\] \[= a_0 + \cfrac{c_{1} a_{1}}{c_{1} b_{1} + \cfrac{c_{1} c_{2} a_{2}}{c_{2} b_{2}+\cfrac{c_{2} c_{3} a_{3}}{c_{3} b_{3}+\cfrac{c_{3} c_{4} a_{4}}{c_{4} b_{4} + \cdots +\cfrac{c_{n-1} c_{n} c_{n+1} a_{n} b_{n+1}}{c_{n} c_{n+1} b_{n} b_{n+1} + c_{n} c_{n+1} a_{n+1}}}}}}\] \[= a_0 + \cfrac{c_{1} a_{1}}{c_{1} b_{1} + \cfrac{c_{1} c_{2} a_{2}}{c_{2} b_{2}+\cfrac{c_{2} c_{3} a_{3}}{c_{3} b_{3}+\cfrac{c_{3} c_{4} a_{4}}{c_{4} b_{4} + \cdots +\cfrac{c_{n-1} c_{n} c_{n+1} a_{n} b_{n+1}}{c_{n} (c_{n+1} b_{n} b_{n+1} + c_{n+1} a_{n+1})}}}}}\]

\[= \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{1} a_{1} & c_{1} b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{1} c_{2} a_{2} & c_{2} b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{2} c_{3} a_{3} & c_{3} b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{3} c_{4} a_{4} & c_{4} b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} c_{n-1} c_{n} a_{n} & c_{n} b_{n} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{n} c_{n+1} a_{n+1} & c_{n+1} b_{n+1} \\ 1 & 0 \end{bmatrix} \] \[= \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{1} a_{1} & c_{1} b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{1} c_{2} a_{2} & c_{2} b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{2} c_{3} a_{3} & c_{3} b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{3} c_{4} a_{4} & c_{4} b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} c_{n-1} c_{n} c_{n+1} a_{n} b_{n+1} & c_{n} c_{n+1} b_{n} b_{n+1} + c_{n} c_{n+1} a_{n+1} \\ 1 & 0 \end{bmatrix} \] \[= \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{1} a_{1} & c_{1} b_{1} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{1} c_{2} a_{2} & c_{2} b_{2} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{2} c_{3} a_{3} & c_{3} b_{3} \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_{3} c_{4} a_{4} & c_{4} b_{4} \\ 1 & 0 \end{bmatrix} \cdot \] \[\cdots \begin{bmatrix} c_{n-1} c_{n} c_{n+1} a_{n} b_{n+1} & c_{n} (c_{n+1} b_{n} b_{n+1} + c_{n+1} a_{n+1}) \\ 1 & 0 \end{bmatrix} \]

and so our result is true for \(n+1\) and thus for all \(n\).

Index

Jump to MathBox

Corollary 3 (Stern-Brocot Continued Fraction)

Let \(H_n\) be the Stern-Brocot continued fraction. That is,
\[H_n = \cfrac{1}{n - \cfrac{1}{1 - \cfrac{1}{2j_2+1 - \cfrac{1}{1 - \cfrac{1}{2j_4+1 - \cdots - \cfrac{1}{2j_{2^{n-1}-1}+1 - \cfrac{1}{1}}}}}}}\]
(where \(j_k\) is the number of factors of 2 in the prime factorisation of \(k\), and \(k=1\) is the first unary term) then
\[H_{n} = [0; n, -1, 2j_2+1, -1, 2j_4+1, -1,..., 2j_{2^{n-1}-1}+1,-1]\] \[= -[0; -n, 1, -2j_2+1, 1, -2j_4+1, 1,..., -2j_{2^{n-1}-1}+1,1]\]
Proof: The first result is by Theorem 1.

The second result is by Theorem 2 and the first result, where \(c_i = -1\).

Index

Jump to MathBox

Index

Jump to MathBox

Index

Jump to MathBox

Mathematics ToolKit

About the MathBoxes...

Hint: When entering mathematical expressions in the math boxes below (f(x), g(x) and h(x)), use the space key to step out of fractions, powers, etc. On Android, begin entry by pressing Enter.

Type simple mathematical expressions and equations as you would normally enter these: for example, "x^2[space]-4x+3", and "2/3[space]". For more interesting elements, use Latex notation (prefix commands such as "sqrt" and "nthroot3" with a backslash (\\)): for example: "\\sqrt(2)[space][space]". Learn More?

Index

To compute an entry, tap the \(f\), \(g\) or \(h\) buttons.

\(f(x)\)

\(g(x)\)

\(h(x)\)

Index

Jump to MathBox

\(a = \)

-1 5 0

\(b = \)

-1 5 0

\(c = \)

-1 5 0

\(d\)

-1 0 5

\(e\)

-1 0 5

App generated by GXWeb

The simple or general form is built by taking the floor (or whole number part) of the fraction at each level and adding the reciprocal of the tail. To convert a real number (n) to a continued fraction is easy! Index Jump to MathBox	The reversal or negative form takes instead the ceiling or next whole number value above, and subtracts the value of the term to form the tail! The reciprocal of this tail then forms the next term in the process. To convert a real number (n) to a negative or reversal continued fraction is just as easy!
Try this yourself? Step 1: Take the integer part of the number - floor[n] or Math.floor(n): This is your first index (call it \(a_0 \)), and first convergent. Step 2: Subtract the integer part to leave the decimal part - the tail. \( Tail = n - floor(n) \) Step 3: Calculate the reciprocal of the tail (\( 1 \over Tail \)) - this should give a number greater than or equal to 1. Step 4: Take the integer part of this reciprocal value (\(a_1 = floor({ 1 \over Tail }) \)): This is your next index - call it \(a_1 \), and \({a_0 + {1 \over a_1}} \) the next convergent. Step 5: Return to Step 2 and repeat the process...	Try this yourself? Step 1: Round up to the integer above the number - ceil[n] or Math.ceil(n): This is your first index (call it \(a_0 \)), and first convergent. Step 2: Subtract the current value from the integer part to leave the decimal part - the tail. \( Tail = ceil(n) - n \) Step 3: Calculate the reciprocal of the tail (\( 1 \over Tail \)) - this should give a number greater than or equal to 1. Step 4: Take the ceiling of this reciprocal value (\(a_1 = ceil({ 1 \over Tail }) \)): This is your next index - call it \(a_1 \), and \({a_0 + {1 \over a_1}} \) the next convergent. Step 5: Return to Step 2 and repeat the process...
\[\frac{10}{7} = [1,2,2,1] \]\[= 1 + \cfrac{1}{2 + \cfrac{1}{2+\cfrac{1}{1}}}\] (Enter 10/7 or 1,2,3 or 1,2,2,1)	\[[\frac{10}{7}]^{-} = [2,2,4]^{-} \]\[= 2 - \cfrac{1}{2 - \cfrac{1}{4}}\] (Enter [10/7]^- or [2,2,4]^- or [10/7]{neg} or [2,2,4]{neg})
\[\frac{43}{30} = [1,2,3,4] \]\[= 1 + \cfrac{1}{2 + \cfrac{1}{3+\cfrac{1}{4}}}\] (Enter 43/30 or 1,2,3,4)	\[[\frac{43}{30}]^{-} = [2,2,5,2,2,2]^{-} \]\[= 2 - \cfrac{1}{2 - \cfrac{1}{5-\cfrac{1}{2-\cfrac{1}{2-\cfrac{1}{2}}}}}\] (Enter [43/30]^- or [2,2,5,2,2,2]^- or [43/30]{neg} or [2,2,5,2,2,2]{neg})

\[...\]	\[12\]	\[12\]	\[12\]	\[12\]	\[12\]	\[6\]	\[a(n)\]
\[...\]	\[1\]	\[1\]	\[1\]	\[1\]	\[1\]	\[(1)\]	\[b(n)\]
\[...\]	\[213442\]	\[17665\]	\[1462\]	\[121\]	\[10\]	\[1\]	\[4\]
\[...\]	\[148183\]	\[12264\]	\[1015\]	\[84\]	\[7\]	\[0\]	\[7\]