I have a first order nonlinear recurrence relation:


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:


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

  • 3
    $\begingroup$ 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. $\endgroup$ – achille hui Aug 24 '16 at 14:11
  • 1
    $\begingroup$ @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 $\endgroup$ – Yuriy S Aug 24 '16 at 14:13
  • $\begingroup$ @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$. $\endgroup$ – Miguel Aug 26 '16 at 15:17
  • 1
    $\begingroup$ @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. $\endgroup$ – Yuriy S Aug 26 '16 at 15:21
  • 1
    $\begingroup$ 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)}$$ $\endgroup$ – 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.

  • $\begingroup$ What is $f^{\circ k}$? $\endgroup$ – leonbloy Jan 8 '17 at 1:15
  • $\begingroup$ @leonbloy It is the $k$-fold composition of $f$. A small circle, symbol for the function composition operation, is added for clarification. $\endgroup$ – Sangchul Lee Jan 8 '17 at 1:18
  • $\begingroup$ But what is $k$? Shouldn't it be $n$? (in the first apparition) $\endgroup$ – leonbloy Jan 8 '17 at 1:19
  • $\begingroup$ @leonbloy, You found a typo! $\endgroup$ – Sangchul Lee Jan 8 '17 at 1:20
  • 1
    $\begingroup$ @ 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 $\endgroup$ – 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 $$

addition, suggested by Winther:

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

  • 2
    $\begingroup$ 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$? $\endgroup$ – Sangchul Lee Jan 8 '17 at 7:22
  • $\begingroup$ Do the terms past $9^{-2n}$ not depend on $a$? $\endgroup$ – robjohn Jan 8 '17 at 7:46
  • $\begingroup$ I expect the remaining terms do depend on $a$. Missing $a^3$ added. $\endgroup$ – GEdgar Jan 8 '17 at 12:28
  • $\begingroup$ 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$$ $\endgroup$ – 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)$

  • $\begingroup$ Without any explanation at all, this risks getting deleted by reviewers - and for good reason. $\endgroup$ – Alex M. Jan 8 '17 at 14:28
  • 1
    $\begingroup$ 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". $\endgroup$ – hardmath Jan 8 '17 at 14:34
  • $\begingroup$ 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,.....$ $$ $$ ? $\endgroup$ – Yuriy S Jan 9 '17 at 12:00
  • $\begingroup$ 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! $\endgroup$ – Yuriy S Jan 9 '17 at 12:02
  • $\begingroup$ 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. $\endgroup$ – Gevorg Hmayakyan Jan 9 '17 at 12:25

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.