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 coprime so the \(p_k / q_k\) are reduced fractions.
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 > 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.