Finite continued fractions

Useful links

Here, we will present another way of approximating real numbers. To be more specific, we will deal with finite continued fractions only in this post.

\pi is an example of a well-known irrational number. Some of its famous approximations are 3,\frac{22}{7}, or \frac{355}{113}. Where do these numbers come from?

Definition: A finite continued fraction (FCF) is any fraction of the form

    \[a_0+\frac{1}{a_1+\frac{1}{...+\frac{1}{a_n}}},\]

where a_0\in\mathbb{R}, a_1,...,a_n\in\mathbb{R}^+. We denote this by [a_0,...,a_n]. A FCF is called pure, if all the coefficients are integers. For our purposes it is sufficient to restrict our attention to pure FCFs.

There also exist infinite continued fractions, which we will deal with in the next post. For example, continued fraction of \pi is infinite, and it looks like [3,7,15,1,292,1,1,1,2,...].

Theorem: A continued fraction of \alpha\in\mathbb{R} is finite if and only if \alpha\in\mathbb{Q}.

Given a FCF, how do we the corresponding rational number? Well, this is very easy. Let’s explore this in the following example.

Example: What is [6,9,2] equal to? By definition, it it equal to

    \[6+\frac{1}{9+\frac{1}{2}}=6+\frac{1}{\frac{19}{2}}=6+\frac{2}{19}=\frac{116}{19}.\]

Exercise: Try doing the same thing and prove that [3,5,8]=\frac{131}{41}, [1,2,3,4]=\frac{43}{30}, and [2,1,5,7]=\frac{102}{47}.

How about the inverse process? For a given rational, how do we determine a FCF? The algorithm works with the floor function and can be formulated as follows:

ALGORITHM
Input: \alpha\in\mathbb{R}
Output: a FCF for \alpha
Initialization: \alpha_0:=\alpha,\ i:=0
Repeat: a_i:=\left\lfloor \alpha_i \right\rfloor; if \alpha_i\in\mathbb{Z} then end else \alpha_{i+1}=\frac{1}{\alpha_1-a_i},\ i:=i+1

Example: We will find a FCF for \alpha=\frac{8}{5}. First of all, we have that \frac{8}{5}=1+\frac{1}{x} for some x. What is the value of x? We see that \frac{3}{5}=\frac{1}{x}, hence x=\frac{5}{3}. So, \frac{8}{5}=1+\frac{1}{1+\frac{1}{y}} for some y. Similarly, \frac{2}{3}=\frac{1}{y}, therefore y=\frac{3}{2}. It follows that \frac{8}{5}=1+\frac{1}{1+\frac{1}{1+\frac{1}{z}}} for some z, which is given by \frac{1}{2}=\frac{1}{z}, hence, z=2 and we conclude that

    \[\frac{8}{5}=1+\frac{1}{1+\frac{1}{1+\frac{1}{2}}}=[1,1,1,2].\]

Exercise: Find a FCF for \frac{4}{3},\frac{25}{7}, and \frac{415}{93}.

Solution: \frac{4}{3}=[1,3],\ \frac{25}{7}=[3,1,1,3],\ \frac{415}{93}=[4,2,6,7].

Remark: A FCF is determined “almost uniqely” by \alpha\in\mathbb{Q}. The only small detail is as follows: if

    \[\frac{p}{q}= a_0+\frac{1}{a_1+\frac{1}{...+\frac{1}{a_n}}},\]

then we can also write

    \[\frac{p}{q}= a_0+\frac{1}{a_1+\frac{1}{...+\frac{1}{a_n-1+\frac{1}{1}}}}.\]

If we insist on the last coefficient to be strictly greater than 1, then the expression of \frac{p}{q} is unique.

Leave a Reply

Your email address will not be published. Required fields are marked *