Continued Fractions

$$\matrix{a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \vphantom{\dfrac{1}{a_3}}}} & & \cr & \ddots & \cr & & + \dfrac{1}{a_{n-1} + \dfrac{1}{a_n}} \cr}.$$ \item{} It can also be written as $[a_0; a_1, a_2, \ldots, a_n]$.


Definition. Let $a_0$ , ... $a_n$ be real numbers, with $a_1$ , ..., $a_n$ positive. A finite continued fraction is an expression of the form

$$\matrix{a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \vphantom{\dfrac{1}{a_3}}}} & & \cr & \ddots & \cr & & + \dfrac{1}{a_{n-1} + \dfrac{1}{a_n}} \cr}.$$

To make the writing easier, I'll denote the continued fraction above by $[a_0; a_1, a_2, \ldots,
   a_n]$ . In most cases, the $a_i$ 's will be integers.


Example.

$$\dfrac{47}{17} = 2 + \dfrac{13}{17} = 2 + \dfrac{1}{\dfrac{17}{13}} = 2 + \dfrac{1}{1 + \dfrac{4}{13}} = 2 + \dfrac{1}{1 + \dfrac{1}{\dfrac{13}{4}}} = 2 + \dfrac{1}{1 + \dfrac{1}{3 + \dfrac{1}{4}}}.$$

In short form, $\dfrac{47}{17} = [2; 1, 3, 4]$ .

A little bit of thought should convince you that you can express any rational number as a finite continued fraction in this way. In fact, the expansion corresponds to the steps in the Euclidean algorithm. First,

$$47 = 2\cdot 17 + 13$$

$$17 = 1\cdot 13 + 4$$

$$13 = 3\cdot 4 + 1$$

$$4 = 4\cdot 1 + 0$$

Rewrite these equations as

$$\dfrac{47}{17} = 2 + \dfrac{13}{17}$$

$$\dfrac{17}{13} = 1 + \dfrac{4}{13}$$

$$\dfrac{13}{4} = 3 + \dfrac{1}{4}$$

You can get the continued fraction I found above by substituting the third equation into the second, and then substituting the result into the first.

Since this is just the Euclidean algorithm, I can use the first two columns of the Extended Euclidean Algorithm table to get the numbers in the continued fraction expansion:

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & a & & q & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 47 & & - & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 17 & & 2 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 13 & & 1 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 4 & & 3 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 1 & & 4 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} }} $$

Notice that the successive quotients 2, 1, 3, and 4 are the numbers in the continued fraction expansion.


Example. Find the finite continued fraction expansion for $\dfrac{117}{17}$ .

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & a & & q & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 117 & & - & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 17 & & 6 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 15 & & 1 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 2 & & 7 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & \cr & 1 & & 2 & \cr height2pt & \omit & & \omit & \cr \noalign{\hrule} }} $$

$$\dfrac{117}{17} = [6; 1, 7, 2] = 6 + \dfrac{1}{1 + \dfrac{1}{7 + \dfrac{1}{2}}}.\quad\halmos$$


Lemma. Every finite continued fraction with integer terms represents a rational number.

Proof. If $a_0 \in \integer$ , then $[a_0]$ is rational.

Inductively, suppose that a finite continued fraction with $n - 1$ "levels" is a rational number. I want to show that

$$\matrix{a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \vphantom{\dfrac{1}{a_3}}}} & & \cr & \ddots & \cr & & + \dfrac{1}{a_{n-1} + \dfrac{1}{a_n}} \cr}$$

is rational.

By induction,

$$\raise0.52in\hbox{$x =$} \matrix{a_1 + \dfrac{1}{a_2 + \dfrac{1}{a_3 + \vphantom{\dfrac{1}{a_4}}}} & & \cr & \ddots & \cr & & + \dfrac{1}{a_{n-1} + \dfrac{1}{a_n}} \cr}$$

is rational.

So

$$\matrix{a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \vphantom{\dfrac{1}{a_3}}}} & & \cr & \ddots & \cr & & + \dfrac{1}{a_{n-1} + \dfrac{1}{a_n}} \cr} \raise0.52in\hbox{$= a_0 + \dfrac{1}{x}$}$$

is the sum of two rational numbers, which is rational as well.


Example. The continued fraction expansion of a rational number is not unique. For example,

$$\dfrac{47}{17} = 2 + \dfrac{1}{1 + \dfrac{1}{3 + \dfrac{1}{4}}} = 2 + \dfrac{1}{1 + \dfrac{1}{3 + \dfrac{1}{3 + \dfrac{1}{1}}}}.$$

And in general,

$$[a_0; a_1, a_2, \ldots, a_{n-1}, a_n] = [a_0; a_1, a_2, \ldots, a_{n-1}, a_n - 1, 1].\quad\halmos$$


I want to talk about infinite continued fractions --- things that look like

$$\matrix{a_0 + \dfrac{1}{a_1 + \dfrac{1}{a_2 + \dfrac{1}{a_3 + \vphantom{\dfrac{1}{a_4}}}}} & & \cr & \ddots & \cr}$$

In preparation for this, I'll look at the effect of truncating a continued fraction.

Definition. The $k^{\rm th}$ convergent of the continued fraction $[a_0; a_1, a_2,
   \ldots, a_n]$ is

$$c_k = [a_0; a_1, a_2, \ldots, a_k].$$

Note that for $k \ge n$ , $c_k = [a_0; a_1, a_2, \ldots,
   a_n]$ .


Example. $[1; 2, 3, 2]$

$$c_0 = 1$$

$$c_1 = 1 + \dfrac{1}{2} = \dfrac{3}{2}$$

$$c_2 = 1 + \dfrac{1}{2 + \dfrac{1}{3}} = \dfrac{10}{7}$$

$$c_3 = 1 + \dfrac{1}{2 + \dfrac{1}{3 + \dfrac{1}{2}}} = \dfrac{23}{16}$$

And $c_4 = c_5 = \cdots =
   \dfrac{23}{16}$ as well.


The next result gives an algorithm for computing the convergents of a continued fraction. It's important for theoretical reasons, too --- I'll need it for several of the proofs that follow. For the theorem, I won't assume that the $a_i$ 's are integers, since I will need the general result later on.

Theorem. Let $a_0$ , $a_1$ , ..., $a_n$ be positive real numbers. Let

$$p_0 = a_0, \quad q_0 = 1$$

$$p_1 = a_1a_0 + 1, \quad q_1 = a_1$$

$$p_k = a_kp_{k-1} + p_{k-2}, \quad q_k = a_kq_{k-1} + q_{k-2}, \qquad k \ge 2.$$

Then the k-th convergent of $[a_0; a_1, a_2, \ldots, a_n]$ is $c_k =
   \dfrac{p_k}{q_k}$ .

Proof. First, note that

$$\raise0.61in\hbox{$[b_0; b_1, \ldots, b_k, b_{k+1}] =$} \matrix{b_0 + \dfrac{1}{b_1 + \dfrac{1}{b_2 + \vphantom{\dfrac{1}{b_3}}}} & & \cr & \ddots & \cr & & + \dfrac{1}{b_{k-1} + \dfrac{1}{b_k + \dfrac{1}{b_{k+1}}}} \cr} \raise0.61in\hbox{$= \left[b_0; b_1, \ldots, b_k + \dfrac{1}{b_{k+1}}\right]$}$$

by regarding the last two terms as a single term.

Note also that $p_0$ , ..., $p_{k-1}$ and $q_0$ , ..., $q_{k-1}$ are the same for these two fractions, since they only differ in the k-th term.

Now I'll start the proof --- it will go by induction on k. For $k = 0$ ,

$$c_0 = a_0 = \dfrac{a_0}{1} = \dfrac{p_0}{q_0}.$$

And for $k = 1$ ,

$$c_1 = a_0 + \dfrac{1}{a_1} = \dfrac{a_1a_0 + 1}{a_1} = \dfrac{p_1}{q_1}.$$

Suppose $k \ge 2$ , and assume that result holds through the k-th convergent. Then

$$c_{k+1} = [a_0; a_1, \ldots, a_k, a_{k+1}] = \left[a_0; a_1, \ldots, a_k + \dfrac{1}{a_{k+1}}\right].$$

Now this is the k-th convergent of a continued fraction, so by induction this is $\dfrac{p_k}{q_k}$ , where $p_k$ and $q_k$ refer to $\left[a_0; a_1, \ldots, a_k +
   \dfrac{1}{a_{k+1}}\right]$ (as opposed to $[a_0; a_1,
   \ldots, a_k, a_{k+1}]$ ). But what are the $p_k$ and $q_k$ for this fraction? They're given inductively by

$$p_k = (k\hbox{-th term})p_{k-1} + p_{k-2}, \quad q_k = (k\hbox{-th term})q_{k-1} + q_{k-2}.$$

Now $p_{k-2}$ , $p_{k-1}$ , $q_{k-2}$ , $q_{k-1}$ are the same for $\left[a_0; a_1, \ldots,
   a_k + \dfrac{1}{a_{k+1}}\right]$ and $[a_0; a_1, \ldots,
   a_k, a_{k+1}]$ , as I noted at the start. On the other hand, the k-th term of $\left[a_0; a_1, \ldots, a_k +
   \dfrac{1}{a_{k+1}}\right]$ is $a_k + \dfrac{1}{a_{k+1}}$ . So

$$c_{k+1} = \dfrac{\left(a_k + \dfrac{1}{a_{k+1}}\right)p_{k-1} + p_{k-2}} {\left(a_k + \dfrac{1}{a_{k+1}}\right)q_{k-1} + q_{k-2}} = \dfrac{a_{k+1}(a_kp_{k-1} + p_{k-2}) + p_{k-1}} {a_{k+1}(a_kq_{k-1} + q_{k-2}) + q_{k-1}} = \dfrac{a_{k+1}p_k + p_{k-1}}{a_{k+1}q_k + q_{k-1}} = \dfrac{p_{k+1}}{q_{k+1}}.$$

(The next to the last equality also follows by induction.) This shows that the result holds for $k + 1$ , so the induction step is complete.


Example. $[1; 2, 1, 2, 1]$

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & $a_k$ & & $p_k$ & & $q_k$ & & $c_k$ & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 1 & & 1 & & 1 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 2 & & 3 & & 2 & & $\dfrac{3}{2} = 1.5$ & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 4 & & 3 & & $\dfrac{4}{3} \approx 1.33333$ & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 2 & & 11 & & 8 & & $\dfrac{11}{8} = 1.375$ & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 15 & & 11 & & $\dfrac{15}{11} \approx 1.36364$ & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

There is a pattern to the computation of the p's and q's which makes things pretty easy. To get the next p, for instance, multiply the current a by the last p and add the next-to-the-last p.

$$\hbox{\epsfysize=3in \epsffile{continued-fractions1.eps}}$$

Notice that the convergents oscillate, and that the fractions which give the convergents are always in lowest terms.


Example. $[1; 1, 3, 1, 3]$

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & $a_k$ & & $p_k$ & & $q_k$ & & $c_k$ & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 1 & & 1 & & 1 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 2 & & 1 & & 2 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 3 & & 7 & & 4 & & $\dfrac{7}{4} = 1.75$ & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 9 & & 5 & & $\dfrac{9}{5} = 1.8$ & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 3 & & 34 & & 19 & & $\dfrac{34}{19} \approx 1.78947$ & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

Again, notice that the convergents oscillate, and that the fractions for the convergents are always in lowest terms.


I'll prove that the convergent fractions are in lowest terms first.

Theorem. Let $a_0$ , $a_1$ , ..., $a_n$ be positive real numbers. Let

$$p_0 = a_0, \quad q_0 = 1$$

$$p_1 = a_1a_0 + 1, \quad q_1 = a_1$$

$$p_k = a_kp_{k-1} + p_{k-2}, \quad q_k = a_kq_{k-1} + q_{k-2}, \qquad k \ge 2.$$

Then

$$p_kq_{k-1} - p_{k-1}q_k = (-1)^{k-1}.$$

Corollary. Let $a_0$ , $a_1$ , ..., $a_n$ be positive integers. Let

$$p_0 = a_0, \quad q_0 = 1$$

$$p_1 = a_1a_0 + 1, \quad q_1 = a_1$$

$$p_k = a_kp_{k-1} + p_{k-2}, \quad q_k = a_kq_{k-1} + q_{k-2}, \qquad k \ge 2.$$

For $k \ge 1$ , $\dfrac{p_k}{q_k}$ is in lowest terms.

Proof. $p_kq_{k-1} - p_{k-1}q_k = (-1)^{k-1} = \pm 1$ implies that $(p_k, q_k) = 1$ .

Proof of the Theorem. I'll induct on k. For $k = 1$ ,

$$p_1q_0 - p_0q_1 = (a_1a_0 + 1)(1) - (a_0)(a_1) = 1 = 1^{1-1}.$$

Take $k > 1$ , and assume the result holds for k. Then

$$p_{k+1}q_k - p_kq_{k+1} = (a_{k+1}p_k + p_{k-1})q_k - p_k(a_{k+1}q_k + q_{k-1}) = p_{k-1}q_k - p_kq_{k-1} =$$

$$-\left(p_kq_{k-1} - p_{k-1}q_k = (-1)^{k-1}\right) = -(-1)^{k-1} = (-1)^k.$$

This proves the result for $k + 1$ , so the general result is true by induction.


Example. I'll show later that $\dfrac{1 + \sqrt{5}}{2}$ (the golden ratio) has the infinite continued fraction expansion $[1; 1, 1, \ldots]$ . Here are the first ten convergents:

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & $a_k$ & & $p_k$ & & $q_k$ & & $c_k$ & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 1 & & 1 & & 1 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 2 & & 1 & & 2 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 3 & & 2 & & 1.5 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 5 & & 3 & & 1.66667 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 8 & & 5 & & 1.6 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 13 & & 8 & & 1.625 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 21 & & 13 & & 1.61538 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 34 & & 21 & & 1.61905 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 55 & & 34 & & 1.61765 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 89 & & 55 & & 1.61818 & \cr height2pt & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

In fact, $\dfrac{1 +
   \sqrt{5}}{2} \approx 1.61803$ . In this case, you can see formally that $[1; 1, 1, \ldots]$ should be $\dfrac{1 + \sqrt{5}}{2}$ . Let

$$\raise0.38in\hbox{$x = $} \matrix{1 + \dfrac{1}{1 + \dfrac{1}{1 + \dfrac{1}{1 + \vphantom{\dfrac{1}{1}}}}} & \cr & \ddots \cr}$$ Notice that x contains a copy of itself as the bottom of the first fraction! So

$$x = 1 + \dfrac{1}{x}, \quad x^2 = x + 1, \quad x^2 - x - 1 = 0.$$

The roots are $\dfrac{1
   \pm \sqrt{5}}{2}$ . Since the fraction is positive, take the positive root to obtain $x = \dfrac{1 + \sqrt{5}}{2}$ .


Contact information

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga