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=11+11+11+11+ 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+1x 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+1x=1+11+1x=1+11+11+1x= 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 x2=x+1 x^2 = x+1 . Since our solution must obey x1x \ge 1 , we quickly see that the solution of interest is our old friend, the golden ratio ϕ=1+52=11+11+11+11+ \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

ϕ1,32,53,85,138,2113,,377233, \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.6180341.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+1n+1n+1n+1n+ x = n + \frac{1}{n+\frac{1}{n+\frac{1}{n+\frac{1}{n+\cdots}}}}

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

n2+4+n2=n+1n+1n+1n+1n+ \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:

a0+1a1+1a2+1a3+=[a0,a1,a2,a3,] 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

[1,1,1,]=5+12[2,2,2,]=2+1[3,3,3,]=13+22[4,4,4,]=5+2[5,5,5,]=29+52 \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=2an=2a. In that case you get the identity a2+1=[a,2a,2a,2a,] \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,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/qp/q, with pp and qq coprime and p>qp>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  pq=n+rq 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 8/3 = 2 + 2/3 . We're interested in applying this to all fractions, including the remainder r/qr/q. Since it's always less that 11, we cannot repeat the process unless we take its reciprocal. Now we have q/r>1q/r > 1 which can be decomposed again. This continues until you have a remainder of 00 or, equivalently, you have a remainder of the form 1/a1/a. Here's an example of this in action:

92/17=5+7/17 92/17 = 5 + 7/17 17/7=2+3/7 17/7 = 2 + 3/7 7/3=2+1/3 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/33/7=12+1/3 7/3 = 2 + 1/3 \to 3/7 = \frac{1}{2+1/3} 17/7=2+3/717/7=2+12+1/3 17/7 = 2 + 3/7 \to 17/7 = 2 + \frac{1}{2+1/3} 92/17=5+7/1792/17=5+12+12+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<qr<q), we know that this algorithm will always terminate for finite pp and qq. Thus, every rational number has a finite continued fraction. The converse holds as well, which means that any number rr is irrational if and only if its continued fraction expansion is infinite. By now, we've essentially shown that n2+1\sqrt{n^2 + 1} and n2+4\sqrt{n^2 + 4} are irrational for all n>1n>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) 1αα=α0=α0+(αα0)  \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:

3=[1,1,2,1,2,1,2,] \sqrt{3} = [1,1,2,1,2,1,2,\dots] 13=[3,1,1,1,1,6,1,1,1,1,6,1,] \sqrt{13} = [3,1,1,1,1,6,1,1,1,1,6,1,\dots] 14=[3,1,2,1,6,1,2,1,6,1,] \sqrt{14} = [3,1,2,1,6,1,2,1,6,1,\dots] 21=[4,1,1,2,1,1,8,1,1,2,1,] \sqrt{21} = [4,1,1,2,1,1,8,1,1,2,1,\dots] 32=[5,1,1,1,10,1,1,1,10,] \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 11, 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 22, then outline a general method for higher periods.

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

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

t=b+tat+ab+1 t = \frac{b+t}{at + ab + 1} at2+abt=b at^2 + abt = b t=a2b2+4abab2a t = \frac{\sqrt{a^2b^2 + 4ab} - ab}{2a}

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

b=2βa2β2+2aβa=[β,a,2β,a,2β,]b=2β,a=1β2+2β=[β,1,2β,1,2β,]b=2β,a=2β2+β=[β,2,2β,2,2β,] \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,) (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, nn, we can start with t=[0,an1,,a1,a0,an1,] t = [0, a_{n-1}, \dots, a_1, a_0, a_{n-1}, \dots] . We can focus on a sub-fraction of tt, tnt_n, which has the form t1=1/a0 t_1 = 1/a_0 tn+1=1an+tn 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 tn t_n in terms of a0a_0:

t2=1a1+t1=a0a1a0+1=p2q2 t_2 = \frac{1}{a_{1} + t_{1}} = \frac{a_0}{a_{1}a_0 + 1} = \frac{p_2}{q_2} t3=1a2+p2q2=q2a2q2+p2=p3q3 t_3 = \frac{1}{a_{2} +\frac{p_2}{q_2}} = \frac{q_2}{a_2q_2 + p_2} = \frac{p_3}{q_3}

 

{pn=qn1qn=an1qn1+pn1=an1qn1+qn2p0=0,q0=1 \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 tn=pnqn=qn1qn 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 ϕ1=[0,1,1,1,] \phi -1 = [0,1,1,1,\dots] we have: Fn=Fn1+Fn2q0=1,q1=1 F_n = F_{n-1} + F_{n-2} \qquad q_0 = 1, q_1 = 1  

n0123456789101112qn1123581321345589144233tn=ϕ1010.50.66...0.60.6250.61530.6190.61760.61820.61800.61810.6180 \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 tn=qn1/qnt_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 qn=an1qn1+qn2q_{n} = a_{n-1}q{n-1} + q{n-2} due to the fact that qn/Fn1q_n/F_n \ge 1 . Due to this, the denominators of the convergents increase rather slowly. Compare this to a CF like 21=[0,2,2,]\sqrt{2}-1=[0,2,2,\dots] , where we have  

n0123456789101112qn125122970169408985237857411386033461tn=2100.50.40.41670.41380.41430.41430.41420.414220.4142130.41421360.414213550.41421356 \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 qnq_n grows, the approximation becomes more accurate. Given some p/qp/q and a real number σ\sigma, you can choose an integer pp such that p/qσ<1/2q|p/q - \sigma| < 1/2q . In words, the rationals become arbitrarily close together as qq 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,an1,,a1,1/t] t = [0,a_{n-1}, \dots, a_1, 1/t ]. q0=1 q_0 = 1 q1=1/t q_1 = 1/t q2=a0/t+1 q_2 = a_0/t + 1 qn=An/t+Bn q_n = A_n/t + B_n

Which yields:

t=qn1qn=An1+Bn1tAn+Bnt t = \frac{q_{n-1}}{q_n} = \frac{A_{n-1} + B_{n-1}t}{A_{n} + B_n t} Bnt2+(AnBn1)tAn1=0 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.

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

Note by Levi Adam Walker
1 week, 4 days ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...