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

*blynn@cs.stanford.edu*💡