]> Continued Fractions - Definition

## 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 $\left[{a}_{1};{a}_{2},{a}_{3},...\right]$ 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}\left({a}_{2}{a}_{3}+1\right)+{a}_{3}}{{a}_{2}{a}_{3}+1}$

Induction proves the recurrence relations:

$\begin{array}{rlr}{p}_{k}& =& {a}_{k}{p}_{k-1}+{p}_{k-2}\\ {q}_{k}& =& {a}_{k}{q}_{k-1}+{q}_{k-2}\end{array}$

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{\left(-1{\right)}^{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}\left(-1{\right)}^{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=\left[1;2,2,2,...\right]$ 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:

$\begin{array}{rlrlrl}& & 1& 2& 2& ...\\ 0& 1\\ 1& 0\end{array}$

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) $×$ (column heading) $+$ (number two to the left):

$\begin{array}{rlrlrlr}& & 1& 2& 2& 2& ...\\ 0& 1& 1& 3& 7& 17& ...\\ 1& 0& 1& 2& 5& 12& ...\end{array}$

Observe

$a=1+\frac{1}{1+\left[1;2,2,2,...\right]}=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.