Fractions of Fractions of Fractions

Numbers can be expressed in several different ways. We are familiar with whole numbers, fractions and decimals. But there is a wide range of other forms, and we examine one of them in this article. Every rational number ${x}$ can be expanded as a continued fraction:

$\displaystyle x = a_0 + \cfrac{1}{ a_1 + \cfrac{1}{ a_2 + \cfrac{1}{ a_3 + \dotsb + \cfrac{1}{a_n} } }} = [ a_0 ; a_1 , a_2 , a_3 , \dots , a_n ]$

where all ${a_n}$ are integers, all positive except perhaps ${a_0}$ . If ${a_n=1}$ we add it to ${a_{n-1}}$ ; then the expansion is unique.

For an irrational number, the expansion continues indefinitely:

$\displaystyle x = a_0 + \cfrac{1}{ a_1 + \cfrac{1}{ a_2 + \cfrac{1}{ a_3 + \ddots } }} = [ a_0 ; a_1 , a_2 , a_3 , \dots ]$

and this expansion is unique.

Construction of the Expansion

For any number ${x}$ , it is a simple matter to write down the continued fraction expansion.

Subtract from ${x}$ its integer part (technically the floor, ${\lfloor x\rfloor}$ ).
This is the first term, ${a_0 = \lfloor x\rfloor \in\mathbb{Z}}$ .
Invert the remainder: ${(x-a_0) = \frac{1}{1/(x-a_0)}}$ .
The denominator is a positive number greater than ${1}$ . Repeat steps 1 to 3 for this quantity.

Rational numbers have expansions that terminate after a finite number of terms. Irrational ones continue infinitely.

A simple example makes the expansion process clear. The basic approximation of ${\pi}$ is ${22/7 = 3 + \frac{1}{7}}$ . A much more accurate approximation is

$\displaystyle \pi \approx \frac{355}{113} = 3 + \frac{16}{113} = 3 + \frac{1}{113/16} = 3 + \cfrac{1}{7 + \cfrac{1}{16} } = [ 3 ; 7, 16 ]$

which gives six decimal places of accuracy: ${[ 3 ; 7, 16 ] = 3.14159292}$

The (irrational) golden number ${\varphi = (1+\sqrt{5})/2}$ has the expansion

$\displaystyle \varphi = 1 + \cfrac{1}{ 1 + \cfrac{1}{ 1 + \cfrac{1}{ 1 + \ddots } }} = [ 1 ; 1 , 1 , 1 , \dots ]$

This is easily shown by means of the quadratic equation ${x^2-x-1=0}$ of which ${x=\varphi}$ is one solution. We use the equation to write

$\displaystyle x = 1 +\frac{1}{x} = 1 + \cfrac{1}{1 + \cfrac{1}{x} } = 1 + \cfrac{1}{1 + \cfrac{1}{ 1 + \cfrac{1}{x} }}$

which may be continued indefinitely, yielding the expression above.

Some Advantages

The continued fraction representation of a rational number is always finite. This contrasts with the usual decimal expansion, where ${1/2}$ has the finite expression ${0.5}$ but ${1/3}$ has the infinite one ${0.3333 \dots }$ .
The continued fraction for an irrational number is always infinite.
The continued fraction expansion is essentially unique. The only condition is that for a rational number we must have ${a_n>1}$ .
The successive approximations obtained by truncating the continued fraction expansion are the best possible approximations for a given size of the denominator.

The approximation ${[ 3 ; 7, 16 ]}$ for ${\pi}$ is excellent, because the first term omitted has denominator ${292}$ making the error very small. In contrast, the denominators in the expansion of the golden number ${\varphi}$ are all unity, so that the truncated expansions converge very slowly. In a sense, the golden number is the “most irrational” number. The convergents are ratios of Fibonacci numbers:

$\displaystyle 1 \qquad 1 + \cfrac{1}{ 1 } = \frac{2}{1} \qquad 1 + \cfrac{1}{ 1 + \cfrac{1}{ 1 }} = \frac{3}{2} \qquad 1 + \cfrac{1}{ 1 + \cfrac{1}{ 1 + \cfrac{1}{ 1 } }} = \frac{5}{3} \qquad \cdots$

Conclusion

Continued fractions are useful in many contexts. For example, the Lanczos algorithm used to approximate the eigenvalues and eigenvectors of large sparse matrices uses these expansions. Continued fractions are also a favourite subject in recreational mathematics.

This brief note barely scratches the surface of the subject. The wikipedia article on continued fractions is a particularly good source of information.

Notice

Booking is now open for an evening course at University College Dublin, Sum-enchanted Evenings, to be given by Peter Lynch. Book online at www.ucd.ie/all/study or by phone (01 7167123).

ThatsMaths