On Continued Fractions

Let \(a_0,\ldots,a_n\) be admissible integers and \(z_{n+1}\geq 1\) a real number. Let \(a'_0,\ldots,a'_n,z'_{n+1}\) be another bunch of integers with the same characteristics. Assume

\[ [a_0,\ldots,a_n,z_{n+1}] = [a'_0,\ldots,a'_n,z'_{n+1}] \]

Then \(a_i=a'_i\) for all \(i\), and \(z_{n+1}=z'_{n+1}\).

PROOF: For \(n=0\) and \(n=1\) this can be seen directly. For \(n>1\) we use mathematical induction and the formula

\[ [x_0,x_1\ldots,x_n] = [x_0,[x_1,\ldots,x_n]] \]

from the definition. QED.

Note that there is still some degree of Non-uniqueness possible:

\[ [a_0,\ldots,a_n,z_{n+1}] = [a_0,\ldots,a_n,z_{n+1}-1,1] . \]

This basically shows that irrational numbers have a unique infinite bracket-representation, while positive rationals have exactly two possible finite representations.

Let \(\lambda_n=[x_0,\ldots,x_n]\) for admissible reals \(x_0,\ldots,x_n\). This value strictly increases for even indices and strictly decreases for odd indices. Moreover all odd values are larger than any even value.

Proof: The statement follows once these formulas are proved for all \(n\): \(\lambda_{2n+1}>\lambda_{2n-1}\), \(\lambda_{2n}<\lambda_{2n-2}\), and \(\lambda_{2n+1}>\lambda_{2n}\). These can be proved by induction. QED.

In particular, series of \(\lambda_n\) has at most two accumulation points. We will soon see that for our application in continued fractions there is always a limit.

Let \(x\geq0\) and \(x=[a_0,a_1,\ldots,a_n,z_{n+1}]\) be its continued fraction expansion with remainder \(z_{n+1}\) (which is guaranteed to be at least \(1\)). Moreover let \(p_n/q_n=[a_0,\ldots,a_n]\) be the \(n\)​-th convergent. Then we have:

\[ x = \frac{z_{n+1}p_n + p_{n-1}}{z_{n+1}q_n + q_{n-1}} . \]

and the convergents can be recursively defined by:

\[\begin{align*} p_{n+1} = a_{n+1}p_n + p_{n-1} , \\ q_{n+1} = a_{n+1}q_n + q_{n-1} , \end{align*}\]

With \(p_{-2},p_{-1}=0,1\) and \(q_{-2},q_{-1}=1,0\).

PROOF: Just define \(p_n\) and \(q_n\) by the above formula. It is not hard to see by induction that the formula for \(x\) holds. After that just replace \(z_{n+1}\) by \(a_{n+1}\) to see that the \(p_n\) and \(q_n\) are the nominator and denominator of the convergents. QED.

Corollary:

\[ p_n q_{n-1} - p_{n-1} q_n = (-1)^n . \]

Just subtract two consecutive convergents from each other to see this. This directly shows that \(p_n\) and \(q_n\) have no common divisor.

From the representation formula of \(x\) together with the coprimness of \(p_n\) and \(q_n\) we see

\[ x - \frac{p_n}{q_n} = \frac{(-1)^{n+1}}{q_n(z_{n+1}q_n+q_{n-1})} . \]

This implies that the convergent's distance strictly decreases on each iteration and that the convergents indeed converge toward \(x\). Since \(a_{n+1}\,\leq\,z_{n+1}\,\leq\,a_{n+1} + 1\) this also implies

\[ \frac{1}{q_n(q_{n+1} + q_n)} \leq \abs{x - \frac{p_n}{q_n}} \leq \frac{1}{q_nq_{n+1}} . \]

Remark: The formula on the error explains very clearly why it is said that the golden ratio \([1,1,1,\ldots]\) is the hardest to approximate irrational number. Small coefficients in the continued fraction expansion lead to small values for \(q_n\) (by the recursion formula) and hence to a big error.

A rational \(p/q\) is called a best approximation of \(x\) if no other rational with smaller denominator approximates \(x\) better or equally well.

Each convergent of \(x\) is a best approximations (but not necessarily the other way around).

PROOF: By the representation formula for \(x\) we see that any real number \(y\) between \(x\) and \(p_n/q_n\) can be written as:

\[ y = \frac{z p_n + p_{n-1}}{z q_n + q_{n-1}} = [a_0,\ldots,a_n,z] . \]

for some \(z\in(z_{n+1},\infty)\). In particular this implies that each rational between \(x\) and \(p_n/q_n\) has \(p_n/q_n=[a_0,\ldots,a_n]\) as convergent. So these rationals have a denominator which is bigger than \(q_n\).

What is with the other side of \(x\)? It is actually equally usefull to just show a stronger statement. In fact, all these rationals on \(p_n/q_n\)​'s side of \(x\) have \([a_0,\ldots,a_n,a]\) for some \(a>a_{n+1}\) as their convergent. This shows that their denominator is even larger than \(q_{n+1}\) (use recursive formula for the convergents to see this). This shows that any rational between \(p_n/q_n\) and \(p_{n+1}/q_{n+1}\) as denominator which is larger than \(q_{n+1}\). QED.

Let \(x\) be a positive real number and \(p/q\) a rational with:

\[ \abs{x - \frac{p}{q}} \leq \frac{1}{2q^2}. \]

Then \(p/q\) is a convergent of \(x\).

PROOF: Let

\[ \frac{p}{q} = \frac{p_n}{q_n} = [a_0, a_1,\ldots, a_n] . \]

By the non-uniqueness for rationals we may choose whether we want \(n\) to be odd or even. We will use this freedom soon. By the assumption of the theorem there is a \(z>1\) such that:

\[ x - \frac{p}{q} = \frac{\pm1}{q_n(zq_n + q_{n-1})} . \]

Compare this with the error estimate for convergents to get a motivation for this weird formula. As said we may choose the parity of \(n\) so that

\[ p_{n-1} q_n - p_n q_{n-1} = (-1)^{n+1} \]

has the same sign as \(x-p/q\). Hence (just recall how we got the error estimate for the convergents)

\[ x = \frac{z p_n + p_{n-1}}{z q_n + q_{n-1}} = [a_0,\ldots,a_n,z] , \]

which shows that \(p/q\) is a convergent of \(x\). QED.