Continued fractions

1 The magic box and convergents

Given a ring \(R\), a

simple continued fraction \([a_0,a_1,\dots , a_n]\) is an expression defined via \([a_0] = a_0\) and \([a_0,\dots ,a_n] = a_0 +\frac 1 {[a_1,\dots ,a_n]}\). In the case that \(R\) has a topology, we can define infinite continued fractions as limits of finite ones. We call the sequence \(r_k = [a_1,\dots ,a_k]\) the convergents of the continued fraction. Some easily verified identities for continued fractions are:

\[ [a_0,\dots ,a_k,\dots ,a_n] = [a_0,\dots ,a_{k-1},[a_k,\dots ,a_n]] \]

\[ [0,a_0,\dots ,a_n] = \frac 1 {[a_0,\dots ,a_n]} \]

The convergents are computable using an algorithm called the magic box. The magic box works as follows: let \(\begin {pmatrix}b_{-2}&b_{-1}\\c_{-2}&c_{-1}\end {pmatrix} = \begin {pmatrix} 0 & 1\\ 1 & 0\end {pmatrix}\) and define \(b_i = b_{i-2} + b_{i-1}a_i\), \(c_i = c_{i-2} + c_{i-1}a_i\). Then \(\frac {b_k}{c_k}\) is \(r_k\), the \(k^{th}\) convergent.

This can be proven by inducting on \(k\). The base case is easy to verify. In general, note that \([a_0,\dots ,a_k] = [a_0,\dots ,a_{k-1}+\frac 1 a_k]]\). Thus we can apply the result for \([a_0,\dots ,a_{k-1}+\frac 1 a_k]]\) to get that the \(n^{th}\) convergent is \(\frac {b_{k-1}+\frac {b_{k-2}}{a_{k}}}{c_{k-1}+\frac {c_{k-2}}{a_k}} = \frac {a_kb_{k-1}+b_{k-2}}{a_kc_{k-1}+c_{k-2}}\).

The reason it is called the magic box is because the entries \(a_i,b_i,c_i\) can be neatly computed in a box as shown below:

		\(a_0\)	\(a_1\)	\(\dots \)	\(a_n\)
\(0\)	\(1\)	\(b_0\)	\(b_1\)	\(\dots \)	\(b_n\)
\(1\)	\(0\)	\(c_0\)	\(c_1\)	\(\dots \)	\(c_n\)

It is worth pointing out that the two rows of the magic box have a symmetry, namely that if a \(0\) is inserted in the beginning of the \(a_i\) sequence, then the values of \(b_n\) and \(c_n\) switch. This corresponds to the second continued fraction identity mentioned at the beginning. Now we will see another symmetry of the magic box, and hence of continued fractions.

The magic box is related to solutions of linear Diophantine equations. Namely, if \([a_0,\dots ,a_n]\) is a continued fraction for \(\frac {b_n}{c_n}\) (the terms in the magic box), then we can find a solution of the equation \(b_nx-c_ny=1\) in the ring generated by the \(a_i\) using the magic box. Namely, we just reverse the order of the \(a_i\) and compute the magic box for \(d_n,e_n\), as shown below:

		\(a_n\)	\(a_{n-1}\)	\(\dots \)	\(a_0\)
\(0\)	\(1\)	\(d_0\)	\(d_1\)	\(\dots \)	\(d_n\)
\(1\)	\(0\)	\(e_0\)	\(e_1\)	\(\dots \)	\(e_n\)

First note that \(d_{n-1}e_{n}-d_{n}e_{n-1} = (-1)^{n}\). Indeed the determinant of the \(2x2\) matrix on the left hand side is clearly \(-1\) verifying the base case. If we plug in the recurrence relation for the magic box, we will inductively get the result. Now the claim is that \(d_n = b_n, d_{n-1} = c_n\). By the symmetry property of the \(d_i\) and \(e_i\) it will then follow that \(e_n = b_{n-1}\), and by the determinant property it will follow that \(e_{n-1} = c_{n-1}\). These identities along with the fact that the magic box computes the convergents will give the identity:

\[ \frac {[a_0,\dots a_n]}{[a_0,\dots a_{n-1}]} = \frac {[a_n,\dots a_0]}{[a_n,\dots a_1]} \]

To show the claim about \(d_n,d_{n-1}\), one simply has to note that the recurrence relation for the magic box is essentially the one used to obtain solutions of linear Diophantine equations from the quotients in the Euclidean algorithm. Namely, \(\frac 1 {[a_1,\dots ,a_n]} = [a_0,\dots ,a_n]-a_0 = \frac {b_n}{c_n}-a_0\) = \(\frac {b_n-c_n a_0}{c_n}\). If by the induction hypothesis we assume that the result holds for continued fractions of length \(n-1\), then the recurrence relation will show that it holds for \(n\). Indeed the calculation shown here is exactly that done via the Euclidean algorithm if \(a_0\) is the floor of the quotient of \(b_n,c_n\). Then the magic box is a repackaging of the usual algorithm that constructs the solutions of linear Diophantine equations.