Continued Fractions

A continued fraction is anything that has the form

$$a_0 + \frac{b_1}{\displaystyle a_1 + \frac{b_2}{\displaystyle a_2 + \frac{b_3}{\displaystyle a_3 + \cdots}}} \mbox{,}$$ (2.1)

where each a_i--a partial denominator--and b_i--a a partial numerator--are objects which can be added, multiplied, or divided. In other words, a_i and b_i are elements of some subset of a field, for all i. Often the partial numerators and denominators are restricted to the set of integers, which is a subset of many fields. The whole continued fraction itself is an element of the field that is a superset of the set containing the partial numerators and denominators. Thus, abstractly, a continued fraction is a number $x \in F$, where Fis an arbitrary field, such that x has the form

$$x = a_0 + b_1(a_1 + b_2(a_2 + b_3(a_3 + \cdots)^{-1})^{-1})^{-1} \mbox{,}$$

where $a_i, b_i \in P$, with $P \subseteq F$, for all $i \geq 0$. Since 0 has no inverse, there is the further condition that

$$(a_i + b_{i+1}(a_{i+1} + \cdots)^{-1})^{-1} \neq 0$$

for all $i \geq 1$. If after some n the expansion () terminates, then the continued fraction is called finite, otherwise it is infinite. If a₀ is an integer, a_i is a positive integer for all $i \geq 1$, and b_i = 1 for all $i \geq 1$, then the continued fraction is called simple, and each a_i is called a partial quotient. For the remainder of the report, every continued fraction discussed is assumed to be simple. Below are some theorems regarding this type of continued fraction.

Suppose that () is simple and terminated after a_n, so that a continued fraction x has the form

$$x = a_0 + \frac{1}{\displaystyle a_1 + ~_{\ddots_{\displays... ...+ \frac{1}{a_{n-1} + \frac{1}{\displaystyle a_n}}}}} \mbox{.}$$ (2.2)

In standard notation, the continued fraction () is denoted $x = [a_0, a_1, \ldots, a_n]$, and if () is infinite, then it is denoted $[a_0, a_1, \ldots]$. The kth convergent of x is the continued fraction $P_k/Q_k = [a_0, a_1, \ldots, a_k]$, where the partial quotients $a_{k+1}, \ldots, a_n$ are truncated from the continued fraction of x. Since x = P_n/Q_n, one would suspect that an investigation of convergents would lead to some insight on the nature of continued fractions. Indeed, convergents are the most important part of the theory of continued fractions. The following theorem is the foundation for almost the whole theory of simple continued fractions.

Theorem 1   For continued fractions of the form (), convergents satisfy the fundamental recurrence relation

$$\frac{P_n}{Q_n} = \frac{a_nP_{n-1} + P_{n-2}}{a_nQ_{n-1} + Q_{n-2}} \mbox{,}$$ (2.3)

where P_-2 = 0, P_-1 = 1, Q_-2 = 1, and Q_-1 = 0.

Another theorem from the theory of simple continued fractions is needed for the development of the rest of the report, which is the following theorem.

Theorem 2   For all $k \geq 0$,

$$P_nQ_{n-1} - Q_nP_{n-1} = (-1)^{n-1} \mbox{.}$$ (2.4)

These two theorems are the only ones from the theory of finite continued fractions, although they apply to infinite continued fractions as well, that will be needed for the study of families of continued fractions. For more information on finite continued fractions see [2], [6], [7], and [8].

Finding the continued fraction for the square root of some positive, non-square integer is an easy process. It proceeds by first adding and subtracting the greatest integer in the square root from the square root, then taking the reciprocal of the reciprocal of the square root minus the greatest integer in it, and then rationalizing the denominator of the resulting fraction. The same process is applied to the new quadratic irrational, and it continues until the resulting surd is the same as one of the previous surds. For example,

$$\begin{eqnarray*}\sqrt{2} & = & 1 + (\sqrt{2} - 1) \\ & = & 1 + \frac{1}{\disp... ... + 1} \\ & = & 1 + \frac{1}{\displaystyle 2 + (\sqrt{2} - 1)}. \end{eqnarray*}$$

Since

$$\sqrt{2} - 1 = \frac{1}{2 + (\sqrt{2} - 1)} = \frac{1}{\disp... ...le 2 + \frac{1}{\displaystyle 2 + _{\displaystyle \ddots}}} ,$$

the continued fraction for $\sqrt{2}$ is

$$\sqrt{2} = 1 + \frac{1}{\displaystyle 2 + \frac{1}{2 + \frac{1}{\displaystyle 2 + _{\displaystyle \ddots}}}}$$

which is $\sqrt{2} = [1, \overline{2}]$ in the standard notation, where the bar covers the repeating partial quotients. This is the most simple example, but continued fraction for any surd can be found using this method. A method which takes less time and paper is given in [6]. The continued fractions of pure quadratic irrationals all have the same structure, which is given in the following theorem.

Theorem 3   If d is a positive, non-square integer, then $\sqrt{d} = [x_0, \overline{x_1, x_2, \ldots , x_2, x_1, 2x_0}]$, where each partial quotient is a positive integer.

There are many patterns among the continued fractions expansions of surds, some of them being more evident than others. In just the short list of continued fractions below,

n	$\sqrt{n}$	n	$\sqrt{n}$
1	1	26	$[5, \overline{10}]$
2	$[1, \overline{2}]$	27	$[5, \overline{5, 10}]$
3	$[1, \overline{1, 2}]$	28	$[5, \overline{3, 2, 3, 10}]$
4	2	29	$[5, \overline{2, 1, 1, 2, 10}]$
5	$[2, \overline{4}]$	30	$[5, \overline{2, 10}]$
6	$[2, \overline{2, 4}]$	31	$[5, \overline{1, 1, 3, 5, 3, 1, 1, 10}]$
7	$[2, \overline{1, 1, 1, 4}]$	32	$[5, \overline{1, 1, 1, 10}]$
8	$[2, \overline{1, 4}]$	33	$[5, \overline{1, 2, 1, 10}]$
9	3	34	$[5, \overline{1, 4, 1, 10}]$
10	$[3, \overline{6}]$	35	$[5, \overline{1, 10}]$
11	$[3, \overline{3, 6}]$	36	6
12	$[3, \overline{2, 6}]$	37	$[6, \overline{12}]$
13	$[3, \overline{1, 1, 1, 1, 6}]$	38	$[6, \overline{6, 12}]$
14	$[3, \overline{1, 2, 1, 6}]$	39	$[6, \overline{4, 12}]$
15	$[3, \overline{1, 6}]$	40	$[6, \overline{3, 12}]$
16	4	41	$[6, \overline{2, 2, 12}]$
17	$[4, \overline{8}]$	42	$[6, \overline{2, 12}]$
18	$[4, \overline{4, 8}]$	43	$[6, \overline{1, 1, 3, 1, 5, 1, 3, 1, 1, 12}]$
19	$[4, \overline{2, 1, 3, 1, 2, 8}]$	44	$[6, \overline{1, 1, 1, 2, 1, 1, 1, 12}]$
20	$[4, \overline{2, 8}]$	45	$[6, \overline{1, 2, 2, 2, 1, 12}]$
21	$[4, \overline{1, 1, 2, 1, 1, 8}]$	46	$[6, \overline{1, 3, 1, 1, 2, 6, 2, 1, 1, 3, 1, 12}]$
22	$[4, \overline{1, 2, 4, 2, 1, 8}]$	47	$[6, \overline{1, 5, 1, 12}]$
23	$[4, \overline{1, 3, 1, 8}]$	48	$[6, \overline{1, 12}]$
24	$[4, \overline{1, 8}]$	49	7
25	5	50	$[7, \overline{14}]$

one can see many patterns, such as: $\sqrt{k^2 + 1} = [k, \overline{2k}]$, $\sqrt{k^2 + 2} = [k, \overline{k, 2k}]$, $\sqrt{(k+1)^2 - 1} = [k, \overline{1, k-1, 1, 2k}]$, and more generally, $\sqrt{k^2 + c} = [k, \overline{2k/c, 2k}]$. Groups of continued fractions whose periods are predictable and static abound, but the more interesting groups whose periods grow are rare and harder to detect.