Continued Fractions

THE ART AND SCIENCE OF MATHEMATICS
Wednesday, October 12
Continued Fractions

Any rational number x can be written as a finite continued fraction:

$\begin{displaymath} x = a_0 + \frac{1}{a_1+\frac{1}{a_2+\ldots \begin{array}{c}\quad \\ \frac{1}{a_{n-1}+\frac{1}{a_n}} \end{array}}} \end{displaymath}$

where a₁, a₂, ...are positive integers and a₀ is an integer, possibly zero.

A shorthand notation for this is:

$\begin{displaymath}[a_0 ; a_1, a_2, \ldots, a_n]. \end{displaymath}$

For example,

$\begin{displaymath} 1 \frac{2}{3} = 1 + \frac{1}{1+\frac{1}{2}} = [1; 1, 2]. \end{displaymath}$

We also consider infinite continued fractions $x=[\alpha_0; \alpha_1, \alpha_2, \ldots]$ . The finite fraction $x_n:=[\alpha_0; \alpha_1, \alpha_2, \ldots, \alpha_n]$ is called the n-th convergent of the continued fraction x. If you do all the divisions and additions, you will get that $x_n=\frac{p_n}{q_n}$ is rational.

To construct a continued fraction expansion for a given number x, we can employ the following idea:

1.

$\frac{1}{a_1+ \ldots}$ is clearly <1, therefore $a_0=\lfloor x \rfloor$ , the largest integer that is $\leq x$ .

2.

After a₀ is found, consider

$\begin{displaymath} x = a_0 + \frac{1}{r_1} \quad \mbox{where} \quad r_1=\frac{1}{x-a_0}= a_1 + \frac{1}{a_2+\ldots}. \end{displaymath}$

Like in (1), $a_1 = \lfloor r_1 \rfloor$ .

3.

For $i \geq 2$ ,

$\begin{displaymath} r_i = \frac{1}{r_{i-1} - a_{i-1}} \quad \mbox{and} \quad a_i = \lfloor r_i \rfloor. \end{displaymath}$

Continued fractions are important because they provide the best approximation for irrational numbers, in the following sense:

Given an irrational number $\alpha$ , out of all the fractions $\frac{p}{q}$ with denominator $q \leq q_n$ , where q_n comes from the nth convergent $\frac{p_n}{q_n}$ , the convergent gives the best approximation

$\begin{displaymath} \vert \alpha - \frac{p_n}{q_n} \vert \leq \vert \alpha - \frac{p}{q} \vert. \end{displaymath}$

The quality of approximation is given by

$\begin{displaymath} \vert \alpha - \frac{p_n}{q_n} \vert < \frac{1}{q_n^2}. \end{displaymath}$

Problems

1.

Find a continued fraction for $1 \frac{5}{7}$ .

2.

Consider an infinite fraction

$\begin{displaymath} x = [1; 1,1,1,\ldots] \equiv [1; \bar{1}]. \end{displaymath}$

(a): Calculate consecutive convergents $\frac{p_1}{q_1}$ , $\frac{p_2}{q_2}$ , $\frac{p_3}{q_3}$ , ... for x. You will see that the p's and q's are very special numbers.
(b): What is x?

3.

Show that x is a finite fraction if and only if x is rational.

4.

Show that if x is a periodic fraction then it is a solution of a quadratic equation with integer coefficients (a quadratic irrational number).