©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!
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 Bates1 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+13−11−13−11−15−11−13−11Convergents ⇒
01,13,12,23,11,32,21,31,10
Explore the Magic Table
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.
107=1+37=1+173=1+12+13=[1,2,3]
[1,2,3]=1+12+13=1+173=1+37=107
Alternatively, you might try the Magic Table method!
The magic table 1, 2 (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
√(37)=>a(n)=[6,12,12,12,12,12,12,...]b(n)=[1,1,1,1,1,1,1...] 6+112+112+112+112+112+112+112...Using the approaches described here is much simpler than, for example, matrix methods to calculate a result such as
√37+47=[1407]⋅√(37)=[1407]⋅[√(37)001]where the linear fractional transformation is the matrix
[1407] and [1001]represents the identity matrix.
... 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!
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
√37+47=[1407]⋅√(37) =>107 and 12184Taking the floor or integer part of both delivers the same result (|107|=|12184|=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 8437 and 1015447. 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(12)=e−1e+1Here we see that the first convergent pair (13 and 24) both deliver floor values of 0. The second pair (115 and 42) give us the next resultant term of 2.
Subsequently, though, |51|=5 and |71|=7. We must continue to the next terms, 122 and (with a little calculation) 559 (4⋅12+1⋅7=55 and 4⋅2+1⋅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.
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°).
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) ⇑
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
π≈0+41+13+45+97+169+2511+3613+4915+6417+8119...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+13−11−13−11=0+13+1−1+13+1−1 ⇒[0,13,12,23,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+14−11−13−11−15−11−13−11 ⇒[0,14,13,25,12,35,34,23,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+13−11−13−11−15−11−13−11 ⇒[0,13,12,23,1,32,21,31,10] 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+14−11−13−11−15−11−13−11−17−11−13−11−15−11−13−11 ⇒[0,14,13,25,12,35,34,23,1,32,43,53,21,52,31,41,10]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)
Try More Examples
Simple (Convergent)
Magic Table
Dimension 1Gosper
Magic Table
Dimension 2Enter 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])?
Building the Fraction Trees
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 (01) and infinity (∞=10) and uses the mediant to add to the Farey Tree and list all the rationals!
So 01⊕10=0+11+0=11
For the left branch of the Stern-Brocot Tree (the Farey Tree):
01⊕11=0+11+1=12
Then 01⊕12=0+11+2=13and 11⊕12=1+11+2=23
For the right branch of the Stern-Brocot Tree:
and 11⊕10=1+11+0=21
Then 21⊕11=2+11+1=32and 21⊕10=2+11+0=31
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 1n and ends with n1.
01 10
11[1001]
L[1011]1+01+112 R[1101]1+10+121
LL[1011][1011][1021]1+02+113 LR[1011][1101][1112]1+11+223 RL[1101][1011][2111]2+11+132 RR[1101][1101][1201]1+20+131 From 11, to get to 12, 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 12, 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+12 and adding 1 gives [0,1,1]=0+11+11.
In the same way, to get to 13 from 11, step LL (or 00). Add another 0 to get ([0,3]) or 1 for ([0,2,1]). For 23 from 11, 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 41 from 11, step RR (or 11). Add another 1 to get ([3]) or 0 for ([2,1]). For 85 from 11, 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?
Explore the Calkin-Wilf Tree
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 aa+b and a+bb iteratively below each fraction ab.
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
11,12,21,13,32,23,31,14,43,35,52,25,53,34,41...
The sequence has the property that each denominator is the next numerator. That means that the nth rational number in the list looks like 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]
=> 73
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)
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 approach7 involves the product of 2 x 2 matrices.
a0+b0a1+b1a2+b2a3+b3a4...=[a0b010]⋅[a1b110]⋅[a2b210]⋅[a3b310]⋅[a4110]...
For example, arithmetic operations can be readily expressed.
[1,2,3,1,2,3,1,2,3,1...]=>1+12+13+11+12+13+11...[1110]⋅[2110]⋅[3110]⋅[1110]⋅[2110]⋅[3110]⋅[1110]... x=1+12+13+1x=4+√(37)7 If...√37=6+112+112+112+112+...=>[6110]⋅[12110]⋅[12110]⋅[12110]⋅[12110]... Then...4+√(37)7=[1407]⋅√37=>[1407]⋅[6110]⋅[12110]⋅[12110]⋅[12110]⋅[12110]...Even less predictable ones:
[2,2,3,1,1,2,3,1,1,2,3...]=>2+12+13+11+11+12+13... [2110]⋅[2110]⋅[3110]⋅[1110]⋅[1110]⋅[2110]⋅[3110]... x−1=1+12+13+11+1x−1x−1=1+12+13+x−1x=4+√(11)3 If...√11=3+13+16+13+16+...=>[3110]⋅[3110]⋅[6110]⋅[3110]⋅[6110]... Then...4+√(11)3=[1403]⋅√11=>[1403]⋅[3110]⋅[3110]⋅[6110]⋅[3110]⋅[6110]...
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=[a0b0000−1a1b1000−1a2b2000−1a3b3000−1a4]Then taking the inverse of M, the first ([1,1]) term gives the reciprocal of the final convergent of the continued fraction:
1inv(M)[1,1]=a0+b0a1+b1a2+b2a3+b3a4A second approach involves the determinants of two square matrices, p and q as follows:
a0+b0a1+b1a2+b2a3+b3a4=det(p)det(q)
p=[a0b0000−1a1b1000−1a2b2000−1a3b3000−1a4] q=[a1b100−1a2b200−1a3b300−1a4]
Some expected relationships...
And even some unexpected ones!
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-Brocot8,9 AND Calkin-Wilf Trees10,11,12, and consequently, listing all possible rationals.
We begin by viewing 2 x 2 matrices in a new way, as defining the mediant:
[abcd]=>ac⊕bd=a+bc+dThen the familiar identity matrix becomes
[1001]=>10⊕01=1+00+1=11Now we define two matrices, which will serve as left (L) and right (R) steps for our tree:
L=[1011]=>12and R=[1101]=>21Then any term a+cb+d of our Stern-Brocot Tree can be represented by a matrix
M=[abcd]=>a+cb+dwith parents ac and bd and determinant 1. Such a matrix can serve as the parent for two further matrices:
M⋅L=[abcd]⋅[1011] M⋅L=[a+bbc+dd] M⋅L=>a+2⋅bc+2⋅d M⋅R=[abcd]⋅[1101] M⋅R=[aa+bcc+d] M⋅R=>2⋅a+b2⋅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 ba!
M=[abcd]=>ba
Beginning with our identity matrix
M=[1001]=>1+00+1=11Notice the parents of 11 are 01 and 10?
We quickly see the effects of a Left and Right step:
M⋅L=[1001]⋅[1011] M⋅L=[1+00+00+10+1] M⋅L=[1011] M⋅L=>1+01+1 M⋅L=>12 M⋅R=[1001]⋅[1101] M⋅R=[1+01+00+00+1] M⋅R=[1101]∗ M⋅R=>1+10+1 M⋅R=>21 Line * shows that the Stern-Brocot parents of 12 are 01 and 11 and the SB parents of 21 are 11 and 10?
Then, for example, RLRR =>
=[2513]=74(SB) and 52(CW) [1101] ⋅ [1110] ⋅ [1101]⋅[1101]
Refer now to the section Building the Fraction Trees to see this process in more detail, and try some for yourself!
A Proposed Alternative Form
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+13+1−1+13+1−1+15+1−1+13+1−1While 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+13−11−13−11−15−11−13−11 =0+13+1−1+13+1−1+15+1−1+13+1−1
Negative (or Reversal) Continued Fractions
Before considering negative terms within continued fractions, a note about the continued fractions of negative numbers.
107=[1,2,3]=1+12+13Begin by observing that
−107≠−1−1−2−1−3(=−25)AND
−107≠1−12−13(=25)However
−107=[−1,−2,−3]=−1+1−2+1−3and (perhaps surprisingly?)
107=[2,2,4]−=2−12−14
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!
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 a0), 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 (1Tail) - this should give a number greater than or equal to 1.
Step 4: Take the integer part of this reciprocal value (a1=floor(1Tail)): This is your next index - call it a1, and a0+1a1 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 a0), 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 (1Tail) - this should give a number greater than or equal to 1.
Step 4: Take the ceiling of this reciprocal value (a1=ceil(1Tail)): This is your next index - call it a1, and a0+1a1 the next convergent.
Step 5: Return to Step 2 and repeat the process...
107=[1,2,2,1]=1+12+12+11 (Enter 10/7 or 1,2,3 or 1,2,2,1)
[107]−=[2,2,4]−=2−12−14 (Enter [10/7]^- or [2,2,4]^-
or [10/7]{neg} or [2,2,4]{neg})4330=[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!
Converting to the Negative Form
With thanks to Morier-Genoud and Ovsienko (2019)5
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)]
Negative Terms in a Continued Fraction
As noted by Knott2, 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.
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.
Proof by Mathematical Induction
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}
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}
(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.
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 Wall6.
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}
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.
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.
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?
a = -1 5 1 b = -1 5 1 c = -1 5 1 d -1 0 5 e -1 0 5 App generated by GXWeb
Continued Fraction Spreadsheet Explorer
This browser-based spreadsheet uses the handsontable JavaScript library.
WolframAlpha: CAS+
Sometimes, to deal with those stubborn, hard to reach problems, you need something stronger!
The powerful Wolfram Alpha online CAS engine will answer almost anything you care to ask - within reason! From the continued fraction of pi to Solve x^2=x+1 to the population of Australia!
GeoGebra
GeoGebra offers another fast and accurate CAS alternative. You may also like to explore the GeoGebra web app.
Timing: Key Signature:
Share with QR Code
QR Codes are a great way to share data and information with others, even when no Internet connection is available. Most modern devices either come equipped with QR readers in-built, or freely available.
The default link here is the GXWeb Jigsaws and Quizzes, but you can use it as an alternative to sending your assessment data via email, web or share with others in your class. You can even use it to send your own messages!
GXWeb Jigsaws and Quizzes
Share Your Results
Enter your name:
My class:
Email to:
Session report length: 0 characters.
Negative (or Reversal) Continued Fractions
Negative Terms in a Continued Fraction
Proof by Mathematical Induction
Timing: Key Signature:
References
1. Bates, B.P. (2014): The Stern-Brocot Continued Fraction
2. Knott, R. Continued Fractions: An Introduction
3. Euler, L Elements of Algebra (2015 paperback English version of the 1765 original) including Lagrange's Additions of 1771 on Continued Fractions. This is Scott L Hecht's modern typeset version, using modern notation for some of the maths, including CFs.
4. Krishnan, G.G. (2016) Continued Fractions Chapter 6
5. Sophie Morier-Genoud and Valentin Ovsienko (2019) Farey Boat: Continued Fractions and Triangulations, Modular Group and Polygon Dissections (Page 4)
6. Wall, H.S. Analytic Theory of Continued Fractions, Dover, Mineola, New York
7. A. van der Poorten An Introduction to Continued Fractions
8. N. J. Wildberger The Stern-Brocot Tree, Matrices and Wedges: Real Numbers and Limits - Math Foundations 97
9. J. M. Rasmussen (JANMR Blog) (2009) The Stern-Brocot Tree of Fractions
10. Ferreira, J and Mendes, A (2016) A calculational approach to path-based properties of the Eisenstein-Stern and Stern-Brocot trees via matrix algebra
11. Gobler, Ben (2022) The Calkin-Wilf Tree: Extensions and Applications
12. Ben Gobler (2023) Listing the Rationals Using Continued Fractions Part 1 (YouTube 15:09)
Behind the Scenes
©2022 Compass Learning Technologies ← GXWeb Climbing Around Fraction Trees → Extending Stern-Brocot and Continued Fractions