The monster continued fraction

My title may have come off as informal or nonspecific. But, in fact, my title could not be more specific.

Define a sequence with initial term: $$S_0=1+\frac{1}{1+\frac{1}{1+\frac1{\ddots}}}$$ It is well-known that $$S_0=\frac{1+\sqrt{5}}{2}$$. I do not write it as such because, in order to describe the next term, we must look at its continued fraction representation. Take every $$1$$ not a numerator and replace it with $$\frac1{1+\frac1{\ddots}}$$ to get: $$S_1=\frac1{1+\frac1{1+\frac1{\ddots}}} +\frac{1}{\frac1{1+\frac1{1+\frac1{\ddots}}}+\frac1{\frac1{1+\frac1{1+\frac1{\ddots}}}+\frac1\ddots}}$$ Repeat to get: $$S_2=\frac1{\frac1{1+\frac1{1+\frac1{\ddots}}}+\frac1\ddots}+\frac{1}{\frac1{\frac1{1+\frac1{1+\frac1{\ddots}}}+\frac1\ddots}+\frac1{\frac1{\frac1{1+\frac1{1+\frac1{\ddots}}}+\frac1\ddots}+\frac1{\ddots}}}$$ One more time, for good measure: $$S_3=\frac{1}{\frac1{\frac1{1+\frac1{1+\frac1{\ddots}}}+\frac1\ddots}+\frac1{\frac1{\frac1{1+\frac1{1+\frac1{\ddots}}}+\frac1\ddots}+\frac1{\ddots}}}+\frac1{\frac{1}{\frac1{\frac1{1+\frac1{1+\frac1{\ddots}}}+\frac1\ddots}+\frac1{\frac1{\frac1{1+\frac1{1+\frac1{\ddots}}}+\frac1\ddots}+\frac1{\ddots}}}+\frac1{\frac{1}{\frac1{\frac1{1+\frac1{1+\frac1{\ddots}}}+\frac1\ddots}+\frac1{\frac1{\frac1{1+\frac1{1+\frac1{\ddots}}}+\frac1\ddots}+\frac1{\ddots}}}+\frac1{\ddots}}}$$ We buzz like fat bees to the question:

$$\text{What is } \lim_{n \to \infty}S_n\text{?}$$

My almost-solution: Define a recursive sequence as follows: $$\eta_0 = 1$$ $$\eta_k = \frac1{\eta_{k-1}+\frac1{\eta_{k-1}+\frac1\ddots}}$$ Notice: $$\eta_k = \frac1{\eta_{k-1}+\eta_k} \implies \eta_k\eta_{k-1}+\eta_k^2-1=0 \implies \eta_k=\frac{-\eta_{k-1}+\sqrt{\eta_{k-1}^2+4}}2$$ We force the square root in the numerator to be positive for obvious reasons. Now, notice: $$S_0 = \eta_0+\eta_1 = \varphi$$ $$S_1 = S_0-\eta_0+\eta_2=\eta_1+\eta_2$$ $$S_2 = S_1-\eta_1+\eta_3 = \eta_2 + \eta_3$$ $$S_3 = S_2-\eta_2+\eta_4 = \eta_3 + \eta_4$$ $$\vdots$$ $$S_n = S_{n-1} - \eta_{n-1} + \eta_{n+1} = \eta_n + \eta_{n+1}$$ By how I defined $$\eta_i$$, we may rewrite the RHS as: $$S_n = \eta_n + \frac{-\eta_n+\sqrt{\eta_n^2+4}}2 \implies S_n = \frac{\eta_n+\sqrt{\eta_n^2+4}}2$$ This may also be obtained by the equivalence (which I noticed visually): $$\eta_k = \frac1{S_{k-1}}$$ For $$k \geq 1$$. I omit the proof of this, although it is simple. With this in mind, we see: $$S_k = \frac{\eta_k+\sqrt{\eta_k^2+4}}2 \implies 2S_k = \eta_k+\sqrt{\eta_k^2+4}$$ $$\implies 2S_k = \frac1{\eta_{k-1}+\eta_k} + \sqrt{\frac1{(\eta_{k-1}+\eta_k)^2 }+4}$$ $$\implies 2S_k = \frac1{\frac1{S_{k-2}} + \frac1{S_{k-1}}} + \sqrt{\frac1{(\frac1{S_{k-2}} + \frac1{S_{k-1}})^2 }+4}$$ Which, as $$k \to \infty$$, becomes the sum of an infinitely nested fraction and the square root of the sum of the reciprocal of a square of an infinitely nested fraction and $$4$$. In theory, this can be evaluated. But I draw my final breath and collapse, dead.

More seriously, what I have done is defined $$S_n$$ recursively, with initial values $$S_0 = \varphi$$ and $$S_1 = \varphi + \frac1{\varphi+\frac1{\ddots}}$$. But I don't know if this converges. An inverse symbolic calculator might find something.

Edit (Solution): it converges to $$\sqrt{2}$$.

• I just wonder how much time you need to type the monster fraction... Dec 8 '19 at 7:29
• @user284331 it's a matter of copying and pasting! It's the emotional toll that you have you watch out for. Dec 8 '19 at 7:29
• Well, Be sure that you don't mistype anything... Dec 8 '19 at 7:47

It's not too hard to show** the sequence $$\eta_k\to\frac{1}{\sqrt{2}}$$ as $$k\to\infty$$, implying your desired $$k\to\infty$$ limit of $$S_k=\eta_k^{-1}$$ is $$\sqrt{2}$$. There is an error in your obtaining a recursion relation for the sequence $$S_k$$: it should read$$\color{limegreen}{2}S_k=\frac{1}{\frac{1}{S_{k-2}}+\frac{1}{S_{k-1}}}+\sqrt{\frac{1}{(\frac{1}{S_{k-2}}+\frac{1}{S_{k-1}})^2}+4}.$$One could also obtain the behaviour of $$S_n$$ from $$\eta_n+\eta_{n+1}$$.

** The convergence is linear. Writing $$\eta_k=\frac{1}{\sqrt{2}}+\epsilon_k$$ gives $$\eta_k^2+4=\frac92+\epsilon_k\sqrt{2}+\epsilon_k^2$$ and $$\sqrt{\eta_k^2+4}=\frac{3}{\sqrt{2}}+\frac13\epsilon_k+O(\epsilon_k^2)$$, whence $$\eta_{k+1}=\frac{1}{\sqrt{2}}-\frac13\epsilon_k+O(\epsilon_k^2)$$ and $$S_k=\eta_k+\eta_{k+1}=\sqrt{2}+\frac23\epsilon_k+O(\epsilon_k^2)$$.

It took me quite a while to wrap my head around what you actually meant here (especially since $$1$$ is essentially used as a variable). Here is my attempt at making this rigorous, as I found the other answers here lacking. This isn't really a question about continued fractions, so let us start by doing away with them.

I will need the Banach fixed-point theorem, which I will state in a very special case:

Banach fixed-point theorem

Suppose that $$I \subset \mathbb{R}$$ is a closed interval (not necessarily bounded), and that $$f \colon I \to I$$ is a contraction. That is, there is a constant $$\alpha \in (0,1)$$ such that $$|f(x)-f(y)|\leq \alpha |x-y|$$ for all $$x,y \in I$$. Then there is a unique (fixed) point $$a \in I$$ such that $$f(a) = a$$, and moreover $$f^n(x) \to a$$ for every $$x \in I$$.

(Here $$f^n$$ means $$n$$-fold function composition. For instance, $$f^3(x) = (f \circ f \circ f)(x) = f(f(f(x)))$$.)

In fact, I will need a slight generalization of this, namely

Banach fixed-point theorem (generalized)

Suppose that $$I \subset \mathbb{R}$$ is a closed interval, that $$f \colon I \to I$$ is some function on $$I$$, and that $$f^k$$ is a contraction for some $$k \geq 1$$. Then $$f$$ has a unique fixed point $$a$$, and moreover $$f^n(x) \to a$$ for every $$x \in I$$.

Neither of these are difficult to prove, but let's not reinvent the wheel ;)

First off, what does the expression $$[\beta;\beta,\beta,\ldots] = \beta + \frac{1}{\beta+\frac{1}{\beta +\frac{1}{\ddots}}}$$ even mean? It means the limit of the sequence with terms (that is, stopping the continued fraction after $$n$$ levels) $$a_n(\beta) = [\beta;\underbrace{\beta,\beta,\ldots,\beta}_\text{n times}],$$ assuming this limit exists. Thinking of $$\beta > 0$$ as fixed, we define $$f_\beta \colon [\beta,\infty) \to [\beta,\infty)$$ through $$f_\beta(x) := \beta + \frac{1}{x},$$ and observe that, crucially, $$a_n = \beta + \frac{1}{a_{n-1}} = f_\beta(a_{n-1}) =f_\beta^2(a_{n-2}) = \cdots = f_\beta^{n}(a_0) = f_\beta^{n}(\beta).$$

While $$f_\beta$$ itself may not be a contraction (depending on the size of $$\beta$$), you can easily compute that $$(f_\beta^2)'(x) = \frac{1}{(1+\beta x)^2}.$$ Thus $$f_\beta^2$$ is a contraction with contraction constant $$(1+\beta^2)^{-2} < 1$$ by the mean value theorem. As a consequence of the second fixed-point theorem above, $$f_\beta$$ has a unique fixed point, let's say $$a(\beta)$$. And moreover, $$a_n(\beta) = f_\beta^n(\beta) \to a(\beta)$$. As has been mentioned in several other comments, a simple quadratic equation shows that, in fact $$a(\beta) = \frac{\sqrt{\beta^2 + 4}+\beta}{2}.$$

The second continued fraction we need comes for free from the above, namely $$g(\beta) := \frac{1}{\beta + \frac{1}{\beta + \frac{1}{\ddots}}} = a(\beta) - \beta = \frac{\sqrt{\beta^2 + 4}-\beta}{2}.$$

The functions $$a,g$$ above are well defined $$(0,\infty) \to (0,\infty)$$, and your $$S_n(\beta)$$ (with $$\beta = 1$$ in your case) is in fact precisely $$S_n(\beta) = a(g^n(\beta)).$$ Now, we want to (yet again) apply Banach's fixed point theorem, but there is a slight technical issue of $$(0,\infty)$$ not being closed. We solve this by noting that for all $$\beta \in [\varphi^{-1},1]$$ we have $$g(\beta) = \frac{\beta^2+4-\beta^2}{2(\sqrt{\beta^2+4}+\beta} = \frac{2}{\sqrt{\beta^2+4}+\beta} \leq 1$$ and $$g(\beta) \geq \frac{2}{\sqrt{1+4}+1} = \varphi^{-1},$$ so we may consider $$g$$ to be a function $$[\varphi^{-1},1] \to [\varphi^{-1},1]$$ instead. Since $$g'(\beta) = \frac{1}{2}\left(\frac{\beta}{\sqrt{\beta^2+4}}-1\right)$$ satisfies $$-1/2 < g'(\beta) < 0$$, we get that $$g$$ is a contraction (with constant $$1/2$$). It therefore has a unique fixed point $$\gamma \in [\varphi^{-1},1]$$, which you can easily compute to be $$\gamma = 1/\sqrt{2}$$, and more importantly $$g^n(\beta) \to \gamma$$ for all $$\beta \in [\varphi^{-1},1]$$.

Finally, using the continuity of $$a$$, we conclude that $$S_n(\beta) =a(g^n(\beta)) \to a\left(\frac{1}{\sqrt{2}}\right) = \sqrt{2}$$ for every $$\beta \in [\varphi^{-1},1]$$, and in particular for $$\beta \equiv 1$$.

(In fact, using a more quantitative version of Banach's fixed point theorem, it is not difficult to show more explicitly that $$|S_n(1)-\sqrt{2}| \leq 2^{1-n}(1-\varphi^{-1})$$, but this post is already significantly longer than I expected...)

• wow. What an incredible first answer. Welcome to MSE! Dec 13 '19 at 23:52

Assume that $$(S_n)_{n\geq 0}$$ converges to a finite limit $$x\geq 0$$. Taking limits in your final equality yields (this works also if $$x=0$$) $$x=\frac{x}{2}+\sqrt{\dfrac{x^2}{4}+4}$$. Hence $$\frac{x}{2}=\sqrt{\dfrac{x^2}{4}+4}$$, and squaring gives you $$0=4$$.

Thus, $$(S_n)_n$$ is divergent.

Edit. From my comments, and as J.G.'s answer confirms, there was some mistake in the recursion ,and $$S_n$$ converges to $$\sqrt{2}$$.

• There might be a problem with your computations: I suspect something is wrong somewhere, because $(\eta_n)$ potentially converges to $\frac{1}{\sqrt{2}}$, and if the relation $\eta_k=\frac{1}{S_{k-1}}$ is correct, $(S_n)$ should converge to $\sqrt{2}$. I have no time today to trackdown the potential mistake. Dec 8 '19 at 7:57
• I have checked numerical examples; the relation seems correct. Let me know if you spot an error. Dec 8 '19 at 8:05
• Then the mistake is somewhere in your three last implications. Dec 8 '19 at 8:08
– J.G.
Dec 8 '19 at 8:08

Hmm. I get $$x={1\over x+{1\over x + \cdots}}={1\over x+ x}={1\over 2x} \qquad \text{if this converges}$$ Then $$2x^2=1 \\ x=\sqrt{1/2}$$ Isn't it so simple?

Experimenting with the convergence. Let $$\text{cf}_1=[1;1,1,1,1,...]$$ be the continued fraction of the value $$x_1$$. Then iterate $$\begin{array} {}\text{cf}_{k+1}&=x_k \star [1;1,1,1,1,...] \\ &\overset{\text{def}}=[x_k; x_k,x_k,x_k,...] \\ x_{k+1}&=\text{eval}(\text{cf}_{k+1}) \end{array}$$ If we start with $$x_1=\varphi \approx 1.61$$ then that iteration diverges.
If we use better $$\begin{array} {}\text{cf}_{k+1}&=x_k \star [0;1,1,1,1,...] \\ &\overset{\text{def}}=[0; x_k,x_k,x_k,...] \\ x_{k+1}&=\text{eval}(\text{cf}_{k+1}) \end{array}$$ and $$x_1=\varphi-1$$ then this converges. By this definition it converges even for larger $$x_1$$. I think the actual proof must be very easy...

• Yes, although that it converges i don’t think is obvious. Dec 10 '19 at 12:57
• @heepo - just added a tiny "inspiration" for a proof which shows it does exactly your last equation("almost solution"); I'm currently too distracted for a deeper involvement. But I think it's really a tiny (but amazing) game! Dec 10 '19 at 14:25

If we define the function $$f:[0,\infty) \to \mathbb{R}$$ $$f(x) = x+\frac{1}{x+\frac{1}{x+\cdots}}$$ Then we may simplify this to $$f(x)^2-xf(x)-1= 0 \Rightarrow f(x) = \frac{x+\sqrt{x^2+4}}{2}.$$ Then notice that $$f^{n-1}(1) = S_n$$, this reduces the problem of finding the limit of $$S_n$$ to finding stable points of the map $$f$$, suppose there exists a stable point of the map $$f$$, call it $$x_0$$. We then have the relation $$x_0 = \frac{x_0+\sqrt{x_0^2+4}}{2} \Rightarrow 0 = 4$$ a contradiction, hence $$\lim_{n \to \infty}S_n$$ does not exist. I also took the liberty of running some numerical tests and it definitely seems to verify that $$S_n$$ diverges as $$n \to \infty$$.

• I have computed up to $S_{15}$, and I get a number very close to $\sqrt{2}$. Would you mind sharing your code? Dec 13 '19 at 22:49