Special project: continued fractions (optional)

A finite regular continued fraction is an expression of the form

$$a_0+{1\over{a_1+{1\over{a_2+{1\over{... +{1\over a_N}}}}}}},$$ (1.8)

where the $a_0,...,a_N$ are integers (called the partial quotients of the continued fraction). This is also denoted

$$a_0+{1\over a_1+} {1\over a_2+} ...{1\over a_N},$$

or

$$[a_0,a_1,...,a_N].$$

Expressing a real number x by its decimal expansion may seem very natural, but of course upon reflection it is an artifact of humans having 10 fingers. The expansion is clearly base-dependent, so that the integers that combine together to yield x would be quite different if we switched from base 10 to base 7. By contrast, note that a regular continued fraction for a real number x supplies an expansion of x in integers that is not base dependent. However strange it may appear on first glance, the continued expansion of x is in this sense more natural than the decimal expansion of x.

A continued fraction as above is a rational number, say ${p_n\over q_n}=[a_0,a_1,...,a_n]$ . If $a_0,a_1,...$ is a sequence of integers such that $\lim_{n\rightarrow \infty} {p_n\over q_n}=x$ , where $x$ is a real number, then we say $x$ has regular (or simple) continued fraction $[a_0,a_1,...]$ with $n^{th}$ convergent ${p_n\over q_n}=[a_0,a_1,...,a_n]$ . Continued fractions occur frequently in other parts of mathematics and even in the analysis of feedback shift register sequences^1.9.

Example 1.10.1  

$$\begin{array}{c} {8\over 5}=1+{3\over 5}= 1+{1\over 5/3}=\ ... ...= 1+{1\over{1+{1\over{1+{1\over{1+{1\over 2}}}}}}}, \end{array}$$

so $1+{1\over 1+} {1\over 1+}{1\over 2}=[1,1,1,2]=8/5$ .

Let $[x]$ denote the greatest integer less than or equal to $x$ , called the integer part of $x$ . Given a rational number $r>0$ , the following two methods will find the continued fraction expansion.

step 1: Let $r_0=r$ , $a_0=[r_0]$ , $r_1=r_0-a_0$ , and let $i=1$ .

step 2: Let $a_i=[r_i^{-1}]$ , replace $r_i$ by $r_i^{-1}-a_i$ .

step 3: If $r_{i}\not= 0$ then replace $i$ by $i+1$ and go to step $2$ . If $r_{i}= 0$ then stop.

The following theorem says that this algorithm, for any rational number $r$ , will terminate.

Theorem 1.10.2   Each rational number $x$ has a continued fraction expansion.

The proof uses the Euclidean algorithm.

proof: We assume $r$ is not an integer. By adding or subtracting a suitable integer, we may assume that $0<r<1$ . Let $r=a/b$ , where $a,b$ are relatively prime integers and $b>1$ . Recall the steps used in the Euclidean algorithm:

Let $r_{-1}=a$ and $r_0=b$ . Let $a_0=0$ , $i=0$ .

step 1: Use the division algorithm to compute integers $q_{i+1}$ and $0\leq r_{i+1}<r_i$ such that

$$r_{i-1}=r_iq_{i+1}+r_{i+1}, 0\leq {r_{i+1}\over r_i}<1,$$

Let $a_{i+1}=q_{i+1}$ .

step 2: If $r_{i+1}\not= 0$ then increment $i$ and go to step 1. If $r_{i+1}=0$ then stop.

Since $r_{-1}=a>r_0=b>r_1>...\geq 0$ , at some point the above algorithm must terminate.

$\Box$

Example 1.10.3  

(a) $8/11=[0, 1, 2, 1, 2]$ ,

(b) $101/100=[1, 100]$ ,

(c) $11/5=[2,5]$ .

Exercise 1.10.4   Check that the continued fractions in the above example are true.

Find the continued fraction expansions of

(a) $21/13$ ,

(b) $21/11$ .

Exercise 1.10.5   Find the continued fraction expansions of the golden ratio $(1+sqrt[5])/2$ , and make a conjecture as to what the nth convergents are.