Continued Fractions for the Greater Good part 1

OK, maybe not for the greater good, but still fun. This first post will be relatively short and sweet, intended to give an introduction for the posts that will follow.

Before the introduction, some motivation courtesy of Wikipedia:

“...decimal representation has some problems. One problem is that many rational numbers lack finite representations in this system. For example, the number $\frac{1}{3}$ is represented by the infinite sequence $(0, 3, 3, 3, 3, \ldots )$. Another problem is that the constant $10$ is an essentially arbitrary choice, and one which biases the resulting representation toward numbers that have some relation to the integer $10$. For example, $\frac{137}{1600}$ has a finite decimal representation, while $\frac{1}{3}$ does not, not because $\frac{137}{1600}$ is simpler than $\frac{1}{3}$, but because $1600$ happens to divide a power of $10$ ($10^6 = 1600 \times 625$). Continued fraction notation is a representation of the real numbers that avoids both these problems. Let us consider how we might describe a number like $\frac{415}{93}$, which is around $4.4624$. This is approximately $4$. Actually it is a little bit more than $4$, about $4 + \frac{1}{2}$. But the $2$ in the denominator is not correct; the correct denominator is a little bit more than $2$  about $2 + \frac{1}{6}$, so $\frac{415}{93}$ is approximately  $$4 + \cfrac{1}{2+\cfrac{1}{6}}.$$ But the $6$ in the denominator is not correct; the correct denominator is a little bit more than $6$, actually $6+\frac{1}{7}$. So $\frac{415}{93}$ is actually  $$4 + \cfrac{1}{2+\cfrac{1}{6 + \cfrac{1}{7}}}.$$  This is exact...”

With this in mind, one can define an infinite continued fraction to be $$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots}}.$$ With the denominators $a_0, a_1, a_2, \ldots$, we can define a recurrence for the finite approximations (convergents) of this value. For example, the zeroth is $a_0$ and the first is $a_0 + \frac{1}{a_1} = \frac{a_0 a_1 + 1}{a_1}$.

The other motivation (the one I actually learned first in real life) for continued fractions comes from $\sqrt{2}$ being represented by an infinite continued fraction. (Instead of saying a probability of $0.01876$, people would rather say a $1$ in $53$ chance.) So we try to write $\sqrt{2} = 1.41421356\ldots$ as $1 + \frac{1}{2.414}$. But, instead, notice that $$\sqrt{2} = 1 + (\sqrt{2} - 1) = 1 + \frac{1}{\sqrt{2} + 1}.$$ Plugging this into itself, we have  $$\sqrt{2} = 1 + \cfrac{1}{1 + 1 + \cfrac{1}{\sqrt{2} + 1}} = 1 + \cfrac{1}{1 + 1 + \cfrac{1}{1 + 1 + \cfrac{1}{\sqrt{2} + 1}}}$$ and notice it can be represented by $(1; 2, 2, 2, \ldots)$.

Define the $n$th convergent to be $\frac{h_n}{k_n}$, so above we have $h_0 = a_0, k_0 = 1$ and $h_1 = a_0 a_1 + 1, k_0 = a_1$.

Claim: $h_n$ and $k_n$ satisfy $$\begin{align*}h_n &= a_n h_{n - 1} + h_{n - 2} \\ k_n &= a_n k_{n - 1} + k_{n - 2} \end{align*}$$  along with $h_{-1} = 1, h_{-2} = 0$ and $k_{-1} = 0, k_{-2} = 1$.

Proof: The fraction $\frac{h_n}{k_n}$ is converted into $\frac{h_{n + 1}}{k_{n + 1}}$ simply by changing $a_n$ to $a_n + \frac{1}{a_{n + 1}}$ in the final denominator. Since  $$\frac{h_n}{k_n} = \frac{a_n h_{n - 1} + h_{n - 2}}{a_n k_{n - 1} + k_{n - 2}}$$ we similarly have $$\begin{align*} \frac{h_{n + 1}}{k_{n + 1}} &= \frac{\left(a_n + \frac{1}{a_{n + 1}}\right) h_{n - 1} + h_{n - 2}}{\left(a_n + \frac{1}{a_{n + 1}}\right) k_{n - 1} + k_{n - 2}} \\ &= \frac{a_{n + 1}(a_n h_{n - 1} + h_{n - 2}) + h_{n - 1}}{a_{n + 1}(a_n k_{n - 1} + k_{n - 2}) + k_{n - 1}} \\ &= \frac{a_{n + 1} h_n + h_{n - 1}}{a_{n + 1} k_n + k_{n - 1}}\end{align*}$$
Thus $h_{n + 1}$ and $k_{n + 1}$ satisfy the same recurrence.

It remains to check the initial conditions work, but note $$\begin{align*}h_0 &= a_0 h_{-1} + h_{-2} = a_0 \cdot 1 + 0 = a_0 \\ k_0 &= a_0 k_{-1} + k_{-2} = a_0 \cdot 0 + 1 = 1\end{align*}$$ and  $$\begin{align*}h_1 &= a_1 h_{0} + h_{-1} = a_0 a_1 + 1 \\ k_1 &= a_1 k_{0} + k_{-1} = a_1 \cdot 1 + 0 = a_1\end{align*}$$ as we checked above.  $\Box$

Check out my next post, where I actually accomplish something with fractions (or at least prepare to accomplish something).

About Bossy Lobster