Definition
A simple continued fraction is an expression of the form
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
Induction proves the recurrence relations:
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
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
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
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.