41
$\begingroup$

My title may have come off as informal or nonspecific. But, for reasons that will soon become clear, my title could not be more specific.

I begin. 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}}}$$ I call it a hydra. Naturally, 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}}$. I But I don't know if this converges, I'm not even in college yet. An inverse symbolic calculator might find something.

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

Any major edits I will detail below.

$\endgroup$
  • 4
    $\begingroup$ I just wonder how much time you need to type the monster fraction... $\endgroup$ – user284331 Dec 8 '19 at 7:29
  • 18
    $\begingroup$ @user284331 it's a matter of copying and pasting! It's the emotional toll that you have you watch out for. $\endgroup$ – Descartes Before the Horse Dec 8 '19 at 7:29
  • $\begingroup$ Well, Be sure that you don't mistype anything... $\endgroup$ – Kevin. S Dec 8 '19 at 7:47
20
$\begingroup$

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)$.

$\endgroup$
8
$\begingroup$

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...)

$\endgroup$
  • 3
    $\begingroup$ wow. What an incredible first answer. Welcome to MSE! $\endgroup$ – clathratus Dec 13 '19 at 23:52
7
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – GreginGre Dec 8 '19 at 7:57
  • $\begingroup$ I have checked numerical examples; the relation seems correct. Let me know if you spot an error. $\endgroup$ – Descartes Before the Horse Dec 8 '19 at 8:05
  • $\begingroup$ Then the mistake is somewhere in your three last implications. $\endgroup$ – GreginGre Dec 8 '19 at 8:08
  • 1
    $\begingroup$ My answer addresses it. $\endgroup$ – J.G. Dec 8 '19 at 8:08
3
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ Yes, although that it converges i don’t think is obvious. $\endgroup$ – Descartes Before the Horse Dec 10 '19 at 12:57
  • $\begingroup$ @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! $\endgroup$ – Gottfried Helms Dec 10 '19 at 14:25
1
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.