# About the solution of the infinite recurrence $f(x,f(x,f(x,f(x,f(…))))=a$

On internet I found some recreational problems as $$3=\sqrt{x+\sqrt{x+\sqrt{x+\sqrt{x+...}}}}$$ $$\frac{1}{2}=\frac{1}{x+\frac{1}{x+...}}$$ $$2=x^{x^{x^{...}}}$$ And the trick to solve them was just to reuse the equation itself inside the equation, so for example obtaining $3=\sqrt{x+3}$ in the first example above, and so on. But this "trick" reminded me of the well known pseudoparadox we could obtain manipulating divergent series as for example the Bolzano's $$1-1+1-1+1-1+...$$ that setting $S=1-1+1-1+1-1+...$ become $$S=1-1+1-1+1-1+...=1-(1-1+1-1+1-1+...)=1-S$$ and therefore $1-1+1-1+1-1+...=S=1/2$. Obviously the error is in assuming that this series has a precise value, naming it $S$.

We obtain other oddities by generalizing the equations above so that $a=\sqrt{x+\sqrt{x+\sqrt{x+\sqrt{x+...}}}}$ would imply $x=a(a-1)$, $a=\frac{1}{x+\frac{1}{x+...}}$ would imply $x=\frac{1}{a}-a$ and $a=x^{x^{x^{...}}}$ would imply $x=a^{\frac{1}{a}}$, that would be quite strange identities for lots of values of $a$.

Then I feel the need to show that the equations above make sense. I think the most obvious way to formalize them was to define them as limits, exempli gratia $$\sqrt{x+\sqrt{x+\sqrt{x+\sqrt{x+...}}}}=\lim_{n\rightarrow \infty}\underbrace { \sqrt{x+\sqrt{x+\sqrt{x+...+\sqrt{x}}}} }_{n \text{ times} }$$

Then, trying to generalize the problem, we want to study the convergence of the sequence of "recursive" function $$F_0(x)=x \\ F_n(x)=f(x,F_{n-1}(x))$$ For example, we obtain the example at the beginning by respectively setting $f(x,y)=\sqrt{x+{y}}$,$f(x,y)=\frac{1}{x+y}$ and $f(x,y)=x^y$.

In case we manage to prove the convergence, naming $l$ the limit of the sequence, we would have that $f(x,l)=l$.

I've tried to study the sequence $x,x^x,x^{x^x},x^{x^{x^{x}}},...$, for $x \in (0,1)$; after noticing that $\underbrace {x^{x^{x^{x}}} }_{2n \text{ times} }\leq \underbrace {x^{x^{x^{x}}} }_{2n+1 \text{ times} }$ and $\underbrace {x^{x^{x^{x}}} }_{2n+1 \text{ times} }\geq \underbrace {x^{x^{x^{x}}} }_{2n+2 \text{ times} }$, I suspected that for very small value, this succession does not converge, somehow oscillating... but I was not able to prove it.

My questions are:

• Is there some related theory about "infinite equations" as discussed here (that is, if my formalization is correct, the convergence of $F_n(x)=f(x,F_{n-1}(x))$)?
• What about the special case of $2=x^{x^{x^{...}}}$? Is there a way to prove or disprove the convergence for $x\in (0,1)$?
-
Fixed point theorems come to mind... –  Asaf Karagila Sep 1 '12 at 0:56
To answer your first question: In a broad way, ergodic theory (en.wikipedia.org/wiki/Ergodic_theory) comes to mind as well. –  JavaMan Sep 1 '12 at 1:44

For your example $x^{x^\ldots}$, for $x \in (0,1)$ the function $f(y) = x^y$ is decreasing on $(0,\infty)$ with limits $1$ and $0$ as $y \to 0+$ and $y \to \infty$, so there is a unique fixed point $L(x)$. This is not $2$, it is $-{\frac {{\it LambertW} \left( -\ln \left( x \right) \right) }{\ln \left( x \right) }}$.
Now we have to investigate stability. We have $f'(L(x)) = \exp(-LambertW(-\ln(x))) \ln(x)$. This is an increasing function on $(0,1)$, and is $-1$ at $x = x_0 \approx 0.06598803585$. So for $1 > x > x_0$ the fixed point is stable: from any starting point close enough to $L(x)$ the sequence will converge to $L(x)$. In fact, it appears that this will be the case for any starting point in $(0,\infty)$. For $x < x_0$ the fixed point is unstable, and the sequence will never converge to $L(x)$ unless it happens to hit exactly $L(x)$.
EDIT: That $x_0 = e^{-e}$. For this value, the fixed point is $1/e$.
Assume $0<x<1$. As seen above, if $x^{x^{x^\cdots}}$ converges at all, then it converges to a number $a$ such that $x^a=a$, that is a fixpoint of the map $f\colon (0,1)\to(0,1)$, $y\mapsto x^y = e^{y\ln x}$. Since $f'(y) = x^y\ln x$, we have $|f'(y)|<1$ at least when $\frac1e<x<1$; then we find a unique fixpoint $a$. However, if $0< x<\frac 1 e$ I am no longer sure; maybe one can ensure contraction after a few steps?