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?
There's an interesting trick to this; you can make a self-referential substitution
It's a weird approach. It seems to work, however, as expanding it retrieves the original infinite fraction:
Treating this substitution as valid, we get . Since our solution must obey , we quickly see that the solution of interest is our old friend, the golden ratio
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 . These finite approximations will give us rational "convergents" which come arbitrarily close to the (irrational) answer. Let’s try doing just that
Notice that this converges to the correct value , 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 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
making the same substitution leads us to the quadratic equation . Looking only at positive solutions leads us to
Since I'll be writing a lot of continued fractions here, it'll be easier if I introduce a shorthand for them:
Using this identity gives us
Things are significantly simpler when . In that case you get the identity
So it seems that only a small portion of possible square-roots () 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 , with and coprime and (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:
In numbers, this is equivalent to saying something like . We're interested in applying this to all fractions, including the remainder . Since it's always less that , we cannot repeat the process unless we take its reciprocal. Now we have which can be decomposed again. This continues until you have a remainder of or, equivalently, you have a remainder of the form . Here's an example of this in action:
The key to turning this into a continued fraction is to move back up the chain, taking the reciprocals of the decomposed reciprocals.
Because the denominator at each step is strictly smaller than that of the first (), we know that this algorithm will always terminate for finite and . Thus, every rational number has a finite continued fraction. The converse holds as well, which means that any number is irrational if and only if its continued fraction expansion is infinite. By now, we've essentially shown that and are irrational for all . Not a bad result, but we're far more ambitious than that.
This algorithm can easily be extended to any real number . You can check that this yields the same algorithm as above when is rational.
I wrote a small program to find the CF expansions of several square roots using this algorithm. Here are some of its results:
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 , 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 , then outline a general method for higher periods.
We can write a basic period-2 continued fraction as , or as
Multiply the top and bottom of the fraction with
Where we only look the the positive solution. This is guaranteed since for all positive . We can extract some special cases where this is simplified:
So we now know the CF expansions of the square roots of , 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, , we can start with . We can focus on a sub-fraction of , , which has the form
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 in terms of :
These are recurrence relations for the numerator and denominator of the convergents of the CF. Taking we have:
Of course, this is just the Fibonacci sequence! The convergents of the CF expansion are given by , 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 due to the fact that . Due to this, the denominators of the convergents increase rather slowly. Compare this to a CF like , where we have
Which converges far faster. This is essentially a result of the pigeonhole principle: as grows, the approximation becomes more accurate. Given some and a real number , you can choose an integer such that . In words, the rationals become arbitrarily close together as increases. Fast-growing sequences will have a CF expansion which will converge more quickly than slow-growing ones. This means that , 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 .
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.