# Does this recurrence have a closed form limit $x_{n+1}=x_n-\frac{a}{3^{2n+1}x_n}$?

I have a first order nonlinear recurrence relation:

$$x_{n+1}=x_n-\frac{a}{3^{2n+1}x_n}$$

Here $a,x_0$ are positive constants and $a<x_0$. (Also $x_0=A+B$ and $a=(A−B)^2$, for some $A,B>0$).

For these conditions the recurrence quickly converges to a certain limit, which depends only on $a,x_0$:

$$\lim_{n \to \infty}x_n=X(a,x_0)$$

I don't know if this limit has closed form or not, and there is no general method for dealing with nonlinear recurrence relations.

Can $X(a,x_0)$ have a closed form and how to obtain it?

I don't need the explicit expression for $x_n$, only the limit.

I tried to turn it into a differential equation, but I don't know if I've done it correctly, and how the solution to the ODE relates to the original problem:

$$x_{n+1}-x_n=-\frac{a}{3^{2n+1}x_n}$$

$$\frac{df(t)}{dt}=-\frac{b}{3^{2t} f(t)}$$

$$\frac{1}{2} f^2=\frac{b}{2\ln 3} 3^{-2t}+C$$

$$f(t)=\sqrt{\frac{a}{3\ln 3} 3^{-2t}+C}$$

If I set:

$$x_n=\sqrt{\frac{a}{3\ln 3} 3^{-2n}+C}$$

I get:

$$C=x_0^2-\frac{a}{3\ln 3}$$

$$\lim_{n \to \infty}x_n=\sqrt{C}=\sqrt{x_0^2-\frac{a}{3\ln 3}}$$

But that's not correct. Does this work only with linear recurrences?

I have also inverted the recurrence:

$$x_n=\frac{1}{2} \left(x_{n+1}+\sqrt{x_{n+1}^2+\frac{4a}{3^{2n+1}}} \right)$$

This works correctly, but I'm not sure how it may help.

• No idea about the closed form. However, it will be easier to work with $y_n = \sqrt{\frac{3^{2n+1}}{a}} x_n$. The recursion reduces to $y_{n+1} = 3\left(y_n - \frac{1}{y_n}\right)$ and no longer depend on $n$ explicitly. – achille hui Aug 24 '16 at 14:11
• @achillehui ,It would be easier, but this sequence is increasing without bound, so I didn't know how to search for the limit in this case – Yuriy S Aug 24 '16 at 14:13
• @YuriyS I cannot even prove that the limit exists :( Could you assume a lower bound for $a$? Otherwise there exist some ill-posed cases, such as $a=3/16$, $x_0=\sqrt{a/3}$, that leads to $x_1=0$. – Miguel Aug 26 '16 at 15:17
• @MiguelAtencia, this will never happen, because $x_0=A+B$ and $a=(A-B)^2$, for some $A,B>0$. I probably should have mentioned it. – Yuriy S Aug 26 '16 at 15:21
• Unless one fixes $x_0$ as a well-chosen function of $a$, the limit $\ell(a,x_0)$ of the sequence $(x_n)$ for the recursion of parameter $a$, if it exists, must truly depend on $(x_0,a)$. To wit, $$cx_{n+1}=cx_n-\frac{c^2a}{3^{2n+1}cx_n}$$ hence $\ell(cx_0,c^2a)=c\ell(x_0,a)$ for every $c>0$ and $\ell(x_0,a)=\sqrt{a}g(x_0/\sqrt{a})$ for some function $g$. In particular, $\ell(x_0,a)=1$ for every $(x_0,a)$ is impossible. On a more positive note, if $\ell(x_0,a)$ exists and is not $0$ and if $$x_n=\ell(x_0,a)+\frac{b}{9^n}+o\left(\frac1{9^n}\right)$$ then $$b=\frac{3a}{8\ell(x_0,a)}$$ – Did Jan 8 '17 at 13:05

I would be astounded if the limit has a nice closed form. Here are some facts I have investigated.

Let $f(z) = 3z - \frac{1}{z}$. Then we easily check that $y_n = \frac{3^n}{\sqrt{a}} x_n$ satisfies $y_{n+1} = f(y_n)$. Thus $x_n$ has the following general form

$$x_n = \frac{\sqrt{a}}{3^n} f^{\circ n}(y_0) = \sqrt{a} F_n\left(\frac{x_0}{\sqrt{a}}\right), \qquad F_n(z) := z \prod_{k=0}^{n-1} \left(1 - \frac{1}{3f^{\circ k}(z)^2} \right).$$

So it suffices to consider the case where $a = 1$ and then investigate the limit of $F_n(z)$ if exists. To this end, we claim the following:

Proposition. Let $I = [-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}]$. Then the limit $F(z) = \lim_{n\to\infty} F_n(z)$ converges and defines a holomorphic function on $\Bbb{C}\setminus I$. Moreover,

1. There exists a finite Borel measure $\mu$ on $\Bbb{R}$ which is supported on $I$ and satisfies \begin{align*} F(z) &= z - \int_I \frac{\mu(d\lambda)}{z-\lambda} \\ &= z - \frac{3}{8z} - \frac{9}{640z^3} - \frac{2241}{465920z^5} - \cdots \quad \text{as } z \to \infty. \end{align*}

2. $F(f(z)) = 3F(z)$.

The proof of this fact is at the end of this answer. Here are some comments:

• Identifying $F$ amounts to identifying the measure $\mu$. Although not entirely sure, it seems to me that $\mu$ is discrete and $\operatorname{supp}(\mu)$ is a Cantor-like set. That is, poles aggregate at uncountably many points and they do not average out. I can hardly imagine of an elementary function which exhibits this kind of behavior, so I suspect that $F$ is not an elementary function.

• On $(\frac{1}{\sqrt{2}}, \infty)$ the function $f$ has inverse. If we denote by $g = f^{-1}$ the inverse, then for each $\epsilon > 0$ we can prove that

$$g^{\circ n}\left(\frac{1}{\sqrt{2}} + \epsilon\right) = \frac{1}{\sqrt{2}} + \frac{\ell + o(1)}{5^n} \qquad \text{as } n\to\infty \tag{*}$$

for some constant $\ell = \ell(\epsilon) \geq$ which depends on $\epsilon$. Then in view of the identity

$$F\left(\frac{1}{\sqrt{2}} + \epsilon\right) = 3^n F\left(g^{\circ n}\left(\frac{1}{\sqrt{2}} + \epsilon\right) \right),$$

if $F(\frac{1}{\sqrt{2}} + \epsilon) \sim c \epsilon^{\alpha}$ for some constants $c > 0$ and $\alpha$, then we must have $\alpha = \frac{\log 3}{\log 5}$. Although I have not formally written down my idea, using a detailed version of $\text{(*)}$ I checked that $F(\frac{1}{\sqrt{2}} + \epsilon) = \Theta(\epsilon^{\alpha})$ for this $\alpha$, where $\Theta$ is a Landau asymptotic notation.

Proof of Proposition. By the extra assumption $a =1$, we have $x_n = F_n(x_0)$ and $y_n = f^{\circ n}(x_0)$. From this, we have the following relations.

$$F_{n+1}(z) = F_n(z) - \frac{1}{3^{2n+1}F_n(z)}, \qquad F_n(z) = 3^{-n} f^{\circ n}(z). \tag{1}$$

Using the first relation in $\text{(1)}$, we have

$$\operatorname{Im}(F_{n+1}(z)) = \operatorname{Im}(F_n(z))\left( 1 + \frac{1}{3^{2n+1}|F_n(z)|^2} \right).$$

In particular, $F_n$ is a Nevanlinna function and thus we can write write $F_n(z)$ as

$$F_n(z) = z - \int_{\Bbb{R}} \frac{\mu_n(d\lambda)}{z-\lambda}$$

for some point mass $\mu_n$ on $\Bbb{R}$. (This can also be proved directly by some tedious algebra.) This representation shows that $F_n(z) = z - \mu_n(\Bbb{R})z^{-1} + \mathcal{O}(z^{-2})$ as $z \to \infty$. Plugging this to the recurrence relation in $\text{(1)}$, we find that

$$\mu_{n+1}(\Bbb{R}) = \mu_n(\Bbb{R}) + \frac{1}{3^{2n+1}}.$$

In particular, the total mass of $(\mu_n)$ is bounded. On the other hand, if $x \in \Bbb{R}\setminus I$, then we easily check that $|f(x)| > |x|$. This implies that

$\text{(2)}$ $F_n$ is finite on $\Bbb{R}\setminus I$, and thus $\mu_n$ is supported on $I$.

$\text{(3)}$ $F_n$ converges on $\Bbb{R}\setminus I$, since $F_n(x)$ is monotone and bounded for each $x \in \Bbb{R}\setminus I$.

So it follows from $\text{(2)}$ that $(\mu_n)$ is weakly compact and hence $F_n$ is a normal family on $\Bbb{C}\setminus I$. Then the first claim follows from the identity theorem together with $\text{(3)}$.

Once we know that $F_n$ converges on $\Bbb{C}\setminus I$, then the second claim follows by taking the limit to $F_n(f(z)) = 3F_{n+1}(z)$. Using this, we can compute the Laurent expansion of $F$ near $\infty$. Since $F$ is an odd function, with $a_n = \int_{\Bbb{R}} \lambda^{2n} \, \mu(d\lambda)$ we have

$$F(z) = z - \sum_{n=0} \frac{a_n}{z^{2n+1}}.$$

Plugging this to the identity $F(f(z)) = 3F(z)$ produces an system of equations for $(a_n)$, from which we can compute $(a_n)$ at least theoretically.

• What is $f^{\circ k}$? – leonbloy Jan 8 '17 at 1:15
• @leonbloy It is the $k$-fold composition of $f$. A small circle, symbol for the function composition operation, is added for clarification. – Sangchul Lee Jan 8 '17 at 1:18
• But what is $k$? Shouldn't it be $n$? (in the first apparition) – leonbloy Jan 8 '17 at 1:19
• @leonbloy, You found a typo! – Sangchul Lee Jan 8 '17 at 1:20
• @ Sangchul Lee, thank you for this great work even though I now suspect my question can be answered by a simple 'no, there is no closed form'. This recurrence is a modified form of one of my 'iterated means', which is why I was curious about another approach – Yuriy S Jan 8 '17 at 11:08

How about asymptotics for a solution? Something like this: $$x_n = 1 + \frac{3a}{8}\;9^{-n} - \frac{81a^2}{640}\;9^{-2n} +\frac{41553a^3}{465920}\;9^{-3n} + O(9^{-4n}) \qquad\text{as } n \to \infty$$

Solution has the form $$x_n = L \cdot F\left(\frac{a}{L^29^n}\right)$$ where $F(z)$ is given by a certain power series: $$F(z) = 1 + \frac{3z}{8} - \frac{81z^2}{640} +\frac{41553z^3}{465920} + \dots$$

• Your asymptotics seems to suggest that $x_n \to 1$ as $n \to \infty$. Are you talking about the relative error between $x_n$ and $\lim x_n$? – Sangchul Lee Jan 8 '17 at 7:22
• Do the terms past $9^{-2n}$ not depend on $a$? – robjohn Jan 8 '17 at 7:46
• I expect the remaining terms do depend on $a$. Missing $a^3$ added. – GEdgar Jan 8 '17 at 12:28
• You seem to be assuming the limit is $1$. If the limit is $L$ then $$\frac{x_n}{L} = 1 + \frac{3a}{8L^2}9^{-n} - \frac{81a^2}{640 L^4} 9^{-2n} + \mathcal{O}\left(\frac{a}{L^2}9^{-n}\right)^3$$ – Winther Jan 9 '17 at 8:32

We can treat this recursion the following way: $x_{{n+1}}=x_{{0}}-\sum _{i=0}^{n}{\frac {a}{g_{{i}}*x_{{i}}}}$, where $g_{i}=3^{2*i+1}$. Lets consider the $x_{i}$ for {$i=1..\infty$}. From this we get the first coefficients of power series for parameter $b=x_0$: We can see that this parameter for $(-1)$ power of $b$ is: $-a/3,-a/3,.....$

For the first power of $b$ it is: $1, 10/9, 91/81, 820/729, 7381/6561, 66430/59049, 597871/531441, 5380840/4782969, 48427561/43046721, 435848050/387420489, 3922632451/3486784401,....$

The general formula is: $({9^n - 1})/(8*9^{n-1})$. The limit of this sequence is $9/8$.

If we continue this way we can calculate next few terms.

$\lim_{n\rightarrow \infty }x \left( n \right) = -(1/3)*a/b+(9/8)*b+(243/640)*b^3/a+(544563/465920)*b^5/a^2+(11164335381/3056435200)*b^7/a^3+(2096947169256609/180476385689600)*b^9/a^4+O(b^{11})$ where $b=x_0$

I just have calculated the first few terms exactly, but if this helps I can provide the general formula for all terms.

For now I can say exacty that the even coefficients for b are 0. And odd cofficients has the form $M(n)/N(n)$ where the $N(n)$ is $\prod_{i=1..n} (9^i - 1)$

• Without any explanation at all, this risks getting deleted by reviewers - and for good reason. – Alex M. Jan 8 '17 at 14:28
• I can help with the math formatting, but surely the "general formula" you have in mind will be more helpful to Readers than "the first few terms". – hardmath Jan 8 '17 at 14:34
• Is there some typo in the end of this sentense:  We can see that this parameter for $(-1)$ power of $b$ is: $-a/3,-a/3,.....$  ? – Yuriy S Jan 9 '17 at 12:00
• If I understand correctly, the gist of your answer is proposed series expansion of the limit in terms of $a,b$. In this case, if you show the explicit form for the coefficients, the answer would be great! – Yuriy S Jan 9 '17 at 12:02
• Yuriy S. Thanks, Yes. I think the expansion in terms of a,b will simplify understanding of the limit. I will try to provide the M(n) as well. It is a lot of mechanical calculations, and will take some time. – Gevorg Hmayakyan Jan 9 '17 at 12:25