Continued Fractions - Definition

Definition

A simple continued fraction is an expression of the form

a_{1} + \frac{1}{a_{2} + \frac{1}{a_{3} + . . .}}

where the $a_{i}$ are a possibly infinite sequence of integers such that $a_{1}$ is nonnegative and the rest of the seqence is positive. We often write $[a_{1}; a_{2}, a_{3}, . . .]$ in lieu of the above fraction. We may also call them regular continued fractions.

Truncating the sequence at $a_{k}$ and computing the resulting expression gives the $k$ th convergent $p_{k} / q_{k}$ for some positive coprime integers $p_{k}, q_{k}$ . The first three convergents are

a_{1}, \frac{a_{1} a_{2} + 1}{a_{2}}, \frac{a_{1} (a_{2} a_{3} + 1) + a_{3}}{a_{2} a_{3} + 1}

Induction proves the recurrence relations:

\begin{aligned} p_{k} & = & a_{k} p_{k - 1} + p_{k - 2} \\ q_{k} & = & a_{k} q_{k - 1} + q_{k - 2} \end{aligned}

for $k \geq 3$ . We can make these relations hold for all $k \geq 1$ by defining $p_{- 1} = 0, q_{- 1} = 1$ and $p_{0} = 1, q_{0} = 0$ . These correspond to the convergents 0 and $∞$ , the most extreme convergents possible for a nonegative integer. They also allows us to show

\frac{p_{k}}{q_{k}} - \frac{p_{k - 1}}{q_{k - 1}} = \frac{(- 1)^{k}}{q_{k} q_{k - 1}}

Thus the difference between successive convergents approaches zero and alternates in sign, so a continued fraction always converges to a real number. This equation also shows that $p_{k}$ and $q_{k}$ are indeed coprime, a small detail glossed over earlier.

A similar induction shows

p_{k} q_{k - 2} - q_{k} p_{k - 2} = a_{k} (- 1)^{k - 1}

and thus $p_{k} / q_{k}$ decreases for $k$ even, and increases for $k$ odd.

Example

We demonstrate how to compute convergents of $a = [1; 2,2,2, . . .]$ in practice. Terry Gagen introduced this to me as the “magic table”. I’ll refer to this method by this name, as I don’t know its official title.

We write the sequence $a_{i}$ left to right, and two more rows are started, one for the $p_{i}$ and one for the $q_{i}$ , which we bootstrap with the zero and infinity convergents:

\begin{aligned} 1 & 2 & 2 & . . . \\ 0 & 1 \\ 1 & 0 \end{aligned}

For each row, we carry out the recurrence relation from left to right. In other words, for each row entry, write in (number to the left) $\times$ (column heading) $+$ (number two to the left):

\begin{aligned} 1 & 2 & 2 & 2 & . . . \\ 0 & 1 & 1 & 3 & 7 & 17 & . . . \\ 1 & 0 & 1 & 2 & 5 & 12 & . . . \end{aligned}

Observe

a = 1 + \frac{1}{1 + [1; 2,2,2, . . .]} = 1 + \frac{1}{a + 1}

Rearranging, we see $a$ must be a solution to $x^{2} = 2$ , but since $a$ is positive (indeed, $a > 1$ ), we have $a = \sqrt{2}$ . We obtain empirical evidence of some of our earlier statements: the convergents $1 / 1, 3 / 2, 7 / 5, 17 / 12, . . .$ approach $\sqrt{2}$ , alternatively overshooting and undershooting the target, but getting closer each time.