Continued Fractions
Continued fractions have been studied for over two thousand years, with one of the first recorded studies being that of Euclid around 300 BC (in his book Elements) when he used them to find the greatest common divisor of two integers (using what is known today as the Euclidean algorithm).
Since then, continued fractions have shown up in a variety of other areas, including, but not limited to,
- rational approximations for real numbers
- solving linear Diophantine equations
- solving Pell's equation
- approximating \(\pi\).
Contents
Types of Continued Fractions - Finite and Infinite
There are two types of continued fractions:
- finite continued fractions
- infinite continued fractions.
A finite continued fraction is a general representation of a real number \(x\) in the form
\[a_{0}+\cfrac{b_{1}}{a_{1}+\cfrac{b_{2}}{a_2+\cfrac{b_{3}}{a_{3}+\cfrac{b_{4}}{\ddots+\frac{b_n}{a_n}}}}},\]
where \(a_{0},a_{1},\ldots\) and \( b_{1},b_{2},\ldots\) are integers and \(n \geq 1\) .
An infinite continued fraction is a general representation of a real number \(x\) in the form
\[a_{0}+\cfrac{b_{1}}{a_{1}+\cfrac{b_{2}}{a_2+\cfrac{b_{3}}{a_{3}+\cfrac{b_{4}}{a_{4}+\ddots}}}},\]
where \(a_{0},a_{1},\ldots\) and \( b_{1},b_{2},\ldots\) are integers.
An infinite continued fraction representation of a real number is in some ways analogous to its decimal expansion. For instance, the equation \(\frac2{11} = 0.181818\ldots\) means that the sequence of truncated decimals \(0.1, 0.18, 0.181, \ldots\) converges to \(\frac2{11}.\) Similarly, an infinite continued fraction
\[a_{0}+\cfrac{b_{1}}{a_{1}+\cfrac{b_{2}}{a_2+\cfrac{b_{3}}{a_{3}+\cfrac{b_{4}}{a_{4}+\ddots}}}}\]
is simply the limit (if it exists) of the sequence of truncated continued fractions
\[a_0,\ \ a_0 + \cfrac{b_1}{a_1},\ \ a_0 + \cfrac{b_1}{a_1+\cfrac{b_2}{a_2}},\ \ a_0 + \cfrac{b_1}{a_1+\cfrac{b_2}{a_2+\cfrac{b_3}{a_3}}},\ \ \ldots.\]
When the \(a_i\) and \(b_j\) are integers, these truncated continued fractions are all rational numbers, just as the truncated decimal expansions are.
Continued fractions have many beautiful properties related to rational approximation, with numerous applications, including solutions to Pell's equation.
Simple Continued Fractions and Rational Numbers
Above, continued fractions were defined by two sets of integers \(a_n\) and \(b_n\).
Now, if we set \(b_n = 1\) \(\forall\) \(n\), then they are called simple continued fractions.
An infinite simple continued fraction representation of a real number \(x\) is in the form
\[\large a_{0}+\frac{1}{a_{1}+\frac{1}{a_2+\frac{1}{a_{3}+\ddots}}},\]
where \(a_0\) is an integer, and \(a_1,a_2,\ldots\) are positive integers. This is often written more compactly in the following ways:
\[ a_{0}+\frac{1}{a_{1}+} \frac{1}{a_{2}+} \frac{1}{a_{3}+} \cdots=[a_{0};a_{1},a_{2},a_{3},\ldots].\]
Similarly, a finite simple continued fraction representation of a real number \(x\) is in the form
\[\large a_{0}+\frac{1}{a_{1}+\frac{1}{a_2+\frac{1}{\ddots + \frac{1}{a_n}}}},\]
As noted above, a finite simple continued fraction is a rational number. The converse is also true, i.e. any rational number \(\frac mn\) can be converted to a finite simple continued fraction, via the Euclidean algorithm: if \(m = nq+r,\) then \(\frac{m}{n} = q + \frac{r}{n} = q + \small{\dfrac{1}{\frac nr}},\) and the process continues by dividing \(n\) by \(r.\) Here is an illustrative example.
Reduce \(-\frac{551}{802}\) to a simple continued fraction.
First, write down the Euclidean algorithm for dividing \(-551\) by \(802:\)
\[\begin{align} -551 &= 802(-1) + 251 \\ 802 &= 251 \cdot 3 + 49 \\ 251 &= 49 \cdot 5 + 6 \\ 49 &= 6 \cdot 8 + 1 \\ 6 &= 1 \cdot 6 + 0. \end{align}\]
Using this, we have
\[\begin{align} -\dfrac{551}{802}= -1 + \dfrac{251}{802} &= -1 + \dfrac{1}{\dfrac{802}{251}} \\\\ &= -1 + \dfrac{1}{3+\dfrac{49}{251}}= -1 + \dfrac{1}{3+\dfrac{1}{\dfrac{251}{49}}} \\\\ &= -1 + \dfrac{1}{3+\dfrac{1}{5+\dfrac{6}{49}}}= -1 + \dfrac{1}{3+\dfrac{1}{5+\dfrac{1}{\dfrac{49}{6}}}} \\\\ &= -1 + \dfrac{1}{3+\dfrac{1}{5+\dfrac{1}{8+\dfrac{1}{6}}}}= -1 + \dfrac{1}{3+} \dfrac{1}{5+} \dfrac{1}{8+} \dfrac{1}{6}. \end{align}\]
Note that the result of the computation can be read off from the quotients in the Euclidean algorithm:
\[-\dfrac{551}{802} = [-1; 3,5,8,6].\ _\square\]
The famous Indian astronomer, Aryabhata, approximated the value of \(\pi\) as \( 3.1416 \) and then expressed it as a continued fraction of the form
\[ \large a+\frac{1}{b+\frac{1}{c+\frac{1}{d}}}, \]
where \( a,b,c,d \) are positive integers. Find \( a+b+c+d\).
\(\)
Details and Assumptions:
- Use the approximation \( \pi = 3.1416 \).
Periodic Continued Fractions
Assuming that \[ 1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\ddots}}} = [1;1,1,1,\ldots] \] equals some real number, find the number.
Write \(k = [1;1,1,1,\ldots].\) Then
\[\begin{align} k &= 1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\ddots}}}& \\ k &= 1+\frac{1}{k}& \\ k^{2}-k-1&=0. \end{align}\]
So \(k = \dfrac{1\pm\sqrt{5}}2,\) but clearly \( k > 1,\) so \(k\) is the golden ratio \(\frac{1+\sqrt{5}}{2}\).
Here is another example:
Assuming it exists, find the value of
\[1+\frac{1}{1+\frac{1}{2+\frac{1}{1+\frac{1}{2+\ddots}}}} = [1;1,2,1,2,\ldots].\]
We have
\[\begin{align} k &= 1 + \frac1{1+\frac1{2+(k-1)}} \\ k-1 &= \frac{k+1}{k+2} \\ k^2+k-2 &=k+1 \\ k^2 &= 3, \end{align}\]
so \(k=\sqrt{3}\) because it is positive.
\[\Large 4+\frac{1}{2+\frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{2+\frac{1}{8+\frac{1}{\ddots} } } } } } } = \sqrt{ A} \]
Find the positive integer \(A\) in the equation above.
\(\)
Details and Assumptions:
- The pattern repeats \(2,1,3,1,2,8 \) infinitely, but the \(4\) comes only one time, i.e. in the beginning.
As with rational numbers, this process can be reversed.
Write \(\sqrt{7}\) as a simple continued fraction.
The idea is to iterate the process of taking the greatest integer and reciprocating, as follows:
\[\begin{align} \sqrt{7} &= 2 + (\sqrt{7}-2) \\ \frac1{\sqrt{7}-2} &= \frac{\sqrt{7}+2}3 = 1 + \frac{\sqrt{7}-1}3 \\ \frac3{\sqrt{7}-1} &= \frac{\sqrt{7}+1}2 = 1 + \frac{\sqrt{7}-1}2 \\ \frac2{\sqrt{7}-1} &= \frac{\sqrt{7}+1}3 = 1 + \frac{\sqrt{7}-2}3 \\ \frac3{\sqrt{7}-2} &= \sqrt{7} + 2 = 4 + (\sqrt{7}-2), \end{align}\]
and the process repeats.
This gives the continued fraction
\[\sqrt{7} = 2 + \frac1{1+\frac1{1+\frac1{1+\frac1{4+\ddots}}}} = [2;1,1,1,4,1,1,1,4,\ldots] = \left[2;{\overline{1,1,1,4}}\right].\ _\square\]
These examples motivate the following theorem about periodic continued fractions.
Let \(r\) be a real number, and suppose \(r = [a_0; a_1, a_2, \ldots]\) is an infinite simple continued fraction expansion of \(r,\) where the \(a_i\) are integers, with \(a_1,a_2,\ldots\) positive. Then the sequence of \(a_i\) is periodic (that is, there is a positive integer \(k\) such that \(a_{n+k} = a_n\) for sufficiently large \(n\)) if and only if \(r\) is the root of a quadratic polynomial with integer coefficients.
This gives a complete description of the real numbers with periodic simple continued fraction expansions. In the special case \(r=\sqrt{D},\) the expansion has many other special and useful properties, related to the solutions to Pell's equation \(x^2-Dy^2=1;\) see the Pell's Equation wiki for details.
Convergents
This section gives an overview of some of the useful general properties of simple continued fractions, with a focus on the problem of rational approximation: what are the "best" approximations of an irrational number by a rational number?
Let \(r\) be a real number. If \(r\) is rational, there is a unique sequence \(a_0,a_1,\ldots,a_k\) of integers, with \(a_1,\ldots,a_k\) positive and \(a_k\ne 1,\) such that \(r = [a_0;a_1,\ldots,a_k].\) Otherwise, if \(r\) is irrational, there is a unique infinite sequence \(a_0,a_1,\ldots\) of integers, with \(a_1,a_2,\ldots\) positive, such that \(r=[a_0;a_1,a_2,\ldots].\) This equality means that the sequence of truncated continued fractions converges to \(r.\)
Let \(P_k\) and \(Q_k\) be given by the following recursive formulas:
\[\begin{align} P_{-1} = 1,\ P_0 = a_0,\ P_k &= a_k P_{k-1} + P_{k-2} \quad (k \ge 1) \\\\ Q_{-1} = 0,\ Q_0 = 1,\ Q_k &= a_k Q_{k-1} + Q_{k-2} \quad (k \ge 1). \end{align}\]
Then \(\frac{P_k}{Q_k}\) equals the \(k^\text{th}\) truncated continued fraction \([a_0; a_1, \ldots, a_k].\)
The fractions \(\frac{P_k}{Q_k}\) are called the convergents to the irrational number \(r.\)
Find the convergents to the golden ratio \(\frac{1+\sqrt{5}}2.\)
In this case, since the continued fraction is \([1; 1,1,\ldots],\) the recursive formula is \(P_k = P_{k-1}+P_{k-2},\) and similarly for \(Q_k.\) So the numerators and denominators of the convergents are consecutive terms of the Fibonacci sequence:
\[\left\{\frac{P_k}{Q_k}\right\}_{k=0}^{\infty} = \left\{ \frac11, \frac21, \frac32, \frac53, \frac85, \frac{13}8, \ldots \right\}.\]
The theorem says that these fractions converge to the golden ratio. \(_\square\)
The continued fraction for \(\pi\) starts out \[[3;7,15,1,292,\ldots].\] Find the first four convergents to \(\pi.\)
Applying the formulas, we get \[\frac31, \frac{22}7, \frac{333}{106}, \frac{355}{113}.\] The second convergent should look somewhat familiar, and the fourth convergent is less well-known but is an amazingly good approximation to \(\pi\): \[\frac{355}{113} = 3.14159292\ldots.\] Notice that it is less than \(\dfrac1{1000000}\) from \(\pi,\) even though its denominator is only \(113.\)
The intuition behind this is that \(a_4=292\) is especially large, and the difference between the fourth and fifth convergent is especially small, since it corresponds to adding \(\frac{1}{292}\) to the bottom-most denominator of the fourth convergent.
This approximation was known to, and used by, Chinese mathematicians in the \(5^\text{th}\) century AD. \(_\square\)
The next section expands on the ideas in the previous example, giving some general properties of convergents and approximation.
Best Approximation
Let \(r\) be an irrational real number and let \(\frac{P_k}{Q_k}\) be its convergents. Then
\(\frac{P_k}{Q_k}\) and \(\frac{P_{k+1}}{Q_{k+1}}\) are on opposite sides of \(r\); the convergents "bounce back and forth" on the left and right side of \(r\) on the number line.
\(\left| \frac{P_{k+1}}{Q_{k+1}}-r\right| < \left| \frac{P_k}{Q_k} - r \right|.\)
\(\left| \frac{P_{k+1}}{Q_{k+1}} - \frac{P_k}{Q_k} \right| = \frac1{Q_kQ_{k+1}}.\) Note that the left side of this equality is exactly the sum of the two quantities in the previous inequality.
Of any consecutive pair of convergents \(\frac{P_k}{Q_k}\) and \(\frac{P_{k+1}}{Q_{k+1}},\) at least one satisfies the inequality \(\left| \frac{P}{Q}-r \right| < \dfrac1{2Q^2}.\) \(\Big(\)Note that the previous inequality implies that they both satisfy \(\left|\frac{P}{Q}-\alpha\right| < \frac1{Q^2}.\Big)\)
If \(\left|\frac{P}{Q}-r\right| < \frac1{2Q^2},\) then \(\frac{P}{Q}\) must be a convergent.
If \(\left|\frac{P}{Q}-r\right| < \left|\frac{P_k}{Q_k}-r\right|,\) then \(Q > Q_k.\) That is, the convergents are "best" approximations to \(r\) in the sense that no other rational number with smaller denominator can get closer to \(r.\) (Note that not all best approximations in this sense are convergents, but all convergents are best approximations.)
If \(\frac PQ\) has the property that \(|P-Qr|\) is smaller than \(|P'-Q'r|\) for any \(Q'<Q,\) then \(\frac PQ\) must be a convergent; and conversely all convergents have this property. (So in this alternate sense of best approximation, convergents are exactly the best approximations.)
This theorem gives a comprehensive picture of the special nature of convergents and their use in giving effective approximations to real numbers.
Other Types of Continued Fractions
There are other recursive expressions similar to continued fractions that are occasionally useful in applications.
One application of general continued fractions is an alternate approximation of square roots, using the following identity:
Prove that \[\sqrt{n}=1+\frac{n-1}{2+\frac{n-1}{2+\frac{n-1}{2+\ddots}}}.\]
Start with \[\sqrt{n}+n=\sqrt{n}+n+1-1.\] Factor the LHS: \[\sqrt{n}(1+\sqrt{n})=1+\sqrt{n}+n-1.\] Divide both sides by \(1+\sqrt{n}:\) \[\sqrt{n}=1+\frac{n-1}{1+\sqrt{n}}.\] Replace \(\sqrt{n}\) in the fraction with the RHS: \[\sqrt{n}=1+\frac{n-1}{2+\frac{n-1}{2+\ddots}},\] and this process can be continued infinitely. \(_\square\)
Truncating these continued fractions gives a sequence converging to \(\sqrt{n},\) which may not converge as fast as the simple continued fraction, but has the advantage that no computation is required to write down the general continued fraction.
The formula gives \[ \sqrt{5} = 1 + \frac4{2+\frac4{2+\frac4{2+\ddots}}}, \] and the truncated continued fractions \[ 1,\ \ 1+\frac42,\ \ 1+\frac4{2+\frac42},\ \ 1+\frac4{2+\frac4{2+\frac42}},\ \ \ldots \] give a sequence \[ 1,\ 3,\ 2,\ \frac73,\ \ldots \] that converges to \(\sqrt{5}.\) Note that it appears to be going much slower than the sequence of convergents to the simple continued fraction \(\sqrt{5} = [2; 4, 4, \ldots],\) which are \[ 2,\ \frac94,\ \frac{38}{17},\ \frac{161}{72},\ \ldots. \]