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 \ge 3$. We can make these relations hold for all $k \ge 1$ by defining $p_{-1} = 0, q_{-1} = 1$ and $p_0 = 1, q_0 = 0$. These correspond to the convergents 0 and $\infty$, 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:

1

2

2

2

2

0

1

1

0

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):

1

2

2

2

2

0

1

1

3

7

17

1

0

1

2

5

12

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 \gt 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.