# 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.

Ben Lynn blynn@cs.stanford.edu 💡