Exploring continued fractions

I have a problem for you, should you choose to accept. But first let's start with an easier problem: how can you solve this for x?

\[ x= \dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1+\cdots}}}} \]

There's an interesting trick to this; you can make a self-referential substitution

$x = 1+\frac{1}{x}$

It's a weird approach. It seems to work, however, as expanding it retrieves the original infinite fraction:

$x = 1+\frac{1}{x}=1+\frac{1}{1+\frac{1}{x}}=1+\frac{1}{1+\frac{1}{1+\frac{1}{x}}}=\cdots$

Treating this substitution as valid, we get $x^2 = x+1$. Since our solution must obey $x \ge 1$, we quickly see that the solution of interest is our old friend, the golden ratio $\phi = \frac{1 + \sqrt{5}}{2} = \frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\cdots}}}}$

So, what did we get from this? It looks like we can approximate this infinite sum by truncating it at a finite number of iterations, which can be a new and interesting way to compute $\phi$. These finite approximations will give us rational "convergents" which come arbitrarily close to the (irrational) answer. Let’s try doing just that

$\phi \approx 1, \frac{3}{2}, \frac{5}{3}, \frac{8}{5}, \frac{13}{8}, \frac{21}{13}, \cdots, \frac{377}{233}, \cdots$

Notice that this converges to the correct value $1.618034$, albeit a bit slowly. The slowest convergence possible with continued fractions, in fact (I'll hint at the proof here). In this sense you can claim that $\phi$ is the “most irrational number”, but that discussion is worthy of its own post. You may also notice that the numerator and denominator of each convergent are all consecutive members of the Fibonacci sequence. This isn’t an accident; we’ll get to that later.

An obvious next step would be to apply this same treatment to a generalized continued fraction (CF) of the form

$x = n + \frac{1}{n+\frac{1}{n+\frac{1}{n+\frac{1}{n+\cdots}}}}$

making the same substitution $x = n + \frac{1}{x}$ leads us to the quadratic equation $x^2 = nx + 1$. Looking only at positive solutions leads us to

$\frac{\sqrt{n^2 +4}+n}{2} = n + \frac{1}{n+\frac{1}{n+\frac{1}{n+\frac{1}{n+\cdots}}}}$

Since I'll be writing a lot of continued fractions here, it'll be easier if I introduce a shorthand for them:

$a_0 + \frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\cdots}}} = [a_0, a_1, a_2, a_3, \dots]$

Using this identity gives us

$\begin{array}{lr} [1,1,1, \dots]= & \frac{\sqrt{5}+1}{2} \\ [2,2,2, \dots]= & \sqrt{2}+1 \\ [3,3,3, \dots]= & \frac{\sqrt{13}+2}{2} \\ [4,4,4, \dots]= & \sqrt{5} + 2 \\ [5,5,5, \dots]= & \frac{\sqrt{29}+5}{2} \end{array}$

Things are significantly simpler when $n=2a$. In that case you get the identity $\sqrt{a^2 + 1} = [a, 2a, 2a, 2a, \dots ]$

So it seems that only a small portion of possible square-roots ($2,5,10,17,26,37,\dots$) have simple continued fractions like this. Let's start to look for more complex patterns.

To get an idea of what they look like, let's flip our approach and focus on the process of getting a continued fraction from a given value. We can start with the case of rational numbers $p/q$, with $p$ and $q$ coprime and $p>q$ (if the converse holds, take the reciprocal and continue). We can expand them as a continued fraction through a modification of Euclid's algorithm. The idea is to repeat the following operation:

$p = nq + r ,\; r<q \quad \to \; \frac{p}{q} = n + \frac{r}{q}$

In numbers, this is equivalent to saying something like $8/3 = 2 + 2/3$. We're interested in applying this to all fractions, including the remainder $r/q$. Since it's always less that $1$, we cannot repeat the process unless we take its reciprocal. Now we have $q/r > 1$ which can be decomposed again. This continues until you have a remainder of $0$ or, equivalently, you have a remainder of the form $1/a$. Here's an example of this in action:

$92/17 = 5 + 7/17$ $17/7 = 2 + 3/7$ $7/3 = 2 + 1/3$

The key to turning this into a continued fraction is to move back up the chain, taking the reciprocals of the decomposed reciprocals. $7/3 = 2 + 1/3 \to 3/7 = \frac{1}{2+1/3}$ $17/7 = 2 + 3/7 \to 17/7 = 2 + \frac{1}{2+1/3}$ $92/17 = 5 + 7/17 \to 92/17 = 5 + \frac{1}{2 + \frac{1}{2+1/3}}$

Because the denominator at each step is strictly smaller than that of the first ($r<q$), we know that this algorithm will always terminate for finite $p$ and $q$. Thus, every rational number has a finite continued fraction. The converse holds as well, which means that any number $r$ is irrational if and only if its continued fraction expansion is infinite. By now, we've essentially shown that $\sqrt{n^2 + 1}$ and $\sqrt{n^2 + 4}$ are irrational for all $n>1$. Not a bad result, but we're far more ambitious than that.

This algorithm can easily be extended to any real number $\alpha$. You can check that this yields the same algorithm as above when $\alpha$ is rational. $\alpha = \lfloor \alpha \rfloor + (\alpha-\lfloor \alpha \rfloor)$ $\frac{1}{\alpha-\lfloor \alpha \rfloor} = \alpha_0 = \lfloor \alpha_0 \rfloor + (\alpha-\lfloor \alpha_0 \rfloor)\$ $\dots$

I wrote a small program to find the CF expansions of several square roots using this algorithm. Here are some of its results:

$\sqrt{3} = [1,1,2,1,2,1,2,\dots]$ $\sqrt{13} = [3,1,1,1,1,6,1,1,1,1,6,1,\dots]$ $\sqrt{14} = [3,1,2,1,6,1,2,1,6,1,\dots]$ $\sqrt{21} = [4,1,1,2,1,1,8,1,1,2,1,\dots]$ $\sqrt{32} = [5,1,1,1,10,1,1,1,10,\dots]$

Evidently, they all repeat as well, but in a periodic way (periodic continued fractions will always yield a quadratic, but we can't prove that until later). So, the fraction expansions we found earlier were effectively for continued fractions of period $1$, limiting ourselves to a subset of possible square roots. There seem to be examples of every period of a given length as well, though most periods tend to be even. I'll expand our method of evaluating infinite continued fractions to periodic fractions for those with a period of $2$, then outline a general method for higher periods.

We can write a basic period-2 continued fraction $t$ as $[0,a,b,a,b,\dots]$, or as $t = \frac{1}{a+\cfrac{1}{b+t}}$

Multiply the top and bottom of the fraction with $b+t$

$t = \frac{b+t}{at + ab + 1}$ $at^2 + abt = b$ $t = \frac{\sqrt{a^2b^2 + 4ab} - ab}{2a}$

Where we only look the the positive solution. This is guaranteed since $\sqrt{a^2b^2 + 4ab} - ab > 0$ for all positive $b,a$. We can extract some special cases where this is simplified:

$\begin{array}{lr} b=2\beta & \frac{\sqrt{a^2\beta^2 + 2a\beta}}{a} = [ \beta, a, 2\beta, a, 2\beta, \dots ] \\ \\ b=2\beta, a=1 & \sqrt{\beta^2 + 2\beta} = [ \beta, 1, 2\beta, 1, 2\beta, \dots ] \\ \\ b=2\beta, a=2 & \sqrt{\beta^2 + \beta} = [ \beta, 2, 2\beta, 2, 2\beta, \dots ] \end{array}$

So we now know the CF expansions of the square roots of $(6, 8, 12, 15, 20, 24, \dots)$, as they all have period-2 infinite continued fractions. But we know that there are more out there with higher periods, so we need to find a general way to find a CF given some fixed period.

For that period, $n$, we can start with $t = [0, a_{n-1}, \dots, a_1, a_0, a_{n-1}, \dots]$. We can focus on a sub-fraction of $t$, $t_n$, which has the form $t_1 = 1/a_0$ $t_{n+1} = \frac{1}{a_{n} + t_{n}}$

We have a recurrence relation which "builds" continued fractions from the bottom up, with a given sequence of numbers. Because this starts at a finite term and builds the fraction from there, we can really only use this as an approximating tool with periodic sequences. The goal now is to expand $t_n$ in terms of $a_0$:

$t_2 = \frac{1}{a_{1} + t_{1}} = \frac{a_0}{a_{1}a_0 + 1} = \frac{p_2}{q_2}$ $t_3 = \frac{1}{a_{2} +\frac{p_2}{q_2}} = \frac{q_2}{a_2q_2 + p_2} = \frac{p_3}{q_3}$

$\left\{ \begin{array}{c} p_n = q_{n-1} \\ q_n = a_{n-1} q_{n-1} + p_{n-1} = a_{n-1} q_{n-1} + q_{n-2} \end{array} \right. p_0 = 0, q_0 = 1$ $t_n = \frac{p_n}{q_n} = \frac{q_{n-1}}{q_n}$

These are recurrence relations for the numerator and denominator of the convergents of the CF. Taking $\phi -1 = [0,1,1,1,\dots]$ we have: $F_n = F_{n-1} + F_{n-2} \qquad q_0 = 1, q_1 = 1$  

$\begin{array} {ccc} n & 0 &1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ q_n & 1 &1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233\\ t_n=\phi -1 & 0 & 1 & 0.5 & 0.66... & 0.6 & 0.625 & 0.6153 & 0.619 & 0.6176 & 0.6182 & 0.6180 & 0.6181 & 0.6180 \end{array}$  

Of course, this is just the Fibonacci sequence! The convergents of the CF expansion are given by $t_n = q_{n-1}/q_n$, which we now know are just consecutive members of the recurrence relation above. Notice, however, that convergence seems a little slow. 12 terms still isn't enough for accuracy up to three decimal places! It turns out that the problem is that the Fibonacci sequence sets a lower bound for sequences of the type $q_{n} = a_{n-1}q{n-1} + q{n-2}$ due to the fact that $q_n/F_n \ge 1$. Due to this, the denominators of the convergents increase rather slowly. Compare this to a CF like $\sqrt{2}-1=[0,2,2,\dots]$, where we have  

$\begin{array} {ccc} n & 0 &1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ q_n & 1 & 2 & 5 & 12 & 29 & 70 & 169 & 408 & 985 & 2378 & 5741 & 13860 & 33461\\ t_n=\sqrt{2} -1 & 0 & 0.5 & 0.4 & 0.4167 & 0.4138 & 0.4143 & 0.4143 & 0.4142 & 0.41422 & 0.414213 & 0.4142136 & 0.41421355 & 0.41421356 \end{array}$  

Which converges far faster. This is essentially a result of the pigeonhole principle: as $q_n$ grows, the approximation becomes more accurate. Given some $p/q$ and a real number $\sigma$, you can choose an integer $p$ such that $|p/q - \sigma| < 1/2q$. In words, the rationals become arbitrarily close together as $q$ increases. Fast-growing sequences will have a CF expansion which will converge more quickly than slow-growing ones. This means that $\phi$, of all the irrational numbers, has the slowest-converging continued fraction. In some sense, this means that it is the "furthest" from every other rational number.

But let's get back to the general recurrence relations. There's still a bit more to say about them before I pose the true problem. We can use the substitution process we developed earlier and feed it into this recurrence relation. We have $t = [0,a_{n-1}, \dots, a_1, 1/t ]$. $q_0 = 1$ $q_1 = 1/t$ $q_2 = a_0/t + 1$ $q_n = A_n/t + B_n$

Which yields:

$t = \frac{q_{n-1}}{q_n} = \frac{A_{n-1} + B_{n-1}t}{A_{n} + B_n t}$ $B_n t^2 + (A_{n} - B_{n-1}) t - A_{n-1} = 0$

Periodic continued fractions are always the solution of a certain quadratic equation! Now here's the challenge: For any quadratic equation with irrational solutions, can the positive solution be given as a periodic continued fraction - or a rational multiple of one? Can every quadratic number be written as a periodic CF?

Postscript: I did some calculations of common non-quadratic numbers using the algorithm above and got these results for their CF expansions.

$\sqrt[3]{2}= [1, 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, 1, 10, \dots]$ $\pi = [3,7,15,1,292,1,1,1,\dots]$ $\gamma = [0, 1, 1, 2, 1, 2, 1, 4, 3, 13, 5, 1, 1, 8, 1, 2, 4, 1, 1, 40, 1,\dots]$ $\zeta(3) = [1 4, 1, 18, 1, 1, 1, 4, 1, 9, 9, 2, 1, 1, 1, 2, 7,\dots]$