A solution to a nonlinear recurrence equation

Question

I am interested in finding a solution to the following recurrence relationship: $$ F_{n+1} = \sqrt{ A + B/F_n } $$ OR equivalently, the equation: $$ S_{n+1} = C + \frac{E}{\sqrt{S_n}} $$ where $A,B, C, E$ are real positive numbers. I would appreciate to have a solution for any value of n, or at least to know if these sequences are bounded, or if they converge at all. The starting points are nonzero positive reals.

Many thanks in advance.

Thanks for those who help. I would like to add to this question, the possibility of having A and B being independently negative. Also, Does taking the absolute value inside the square root force convergence? I mean: is the relation $$ F_{n+1} = \sqrt{ |A + B/F_n | } $$ better ( i.e. more guaranteed, i.e. wider range of possibilities ) to converge than the one above for any real value for A and B (positive or negative)? Since F(0) is nonzero positive, we cannot be sure that F(n) is not zero now we are having negative values for A and/or B. So, any guess of a starting point to guarantee convergence at this case is also well appreciated.

Note: I was reading the work of Rabinovic http://www.math.tamu.edu/~berko/papers/pdf/jmpRBH96.pdf ) , and I think the theorem reported therein can be a great basis for solving any nonlinear recursion if it could be written as a polynomial. A strategy that comes in my mind is: To expand the relation using Taylor series, and then write the general polynomial term as a function of F(n) . Then use the theorem reported in the that paper, Is this idea sound?

Sorry for long blathering

Answer 1

HINT

Consider the sequence $(F_n)_{n \ge 0}$, given by the recurrence relation $$ F_{n+1} = \sqrt{A+ \frac{B}{F_n}}, \quad F_0, A, B \in \mathbb{R}^+. $$ If this sequence converges to some limit $F$, then $F$ must satisfy $$ F = \sqrt{A + B/F} $$ so you must solve $F^3 - AF - B = 0$, which has exact solutions using Cardano's formula. At least one of them is guaranteed to be real.

---

The second recurrence will similarly lead to $$(S-C)^2 = \frac{E^2}{S},$$ which is a cubic as well...

Answer 2

As shown in the answer of gt6989b, possible limits satisfy the equation $F^3-AF-B=0$.
Claim 1: This equation has exactly one positive solution.
Consider $h(x)=x^3-Ax-B$. Since $h(0)<0$ and $h(x)\to+\infty$ and $x\to\infty$, there is at least one positive solution. Now $h'(x)=3x^2-A$. Therefore $h'(x)<0$ for $x\in]0,\sqrt{A/3}[$ whereas $h'(x)>0$ for $x>\sqrt{A/3}$. Hence $h$ is decreasing on $[0,\sqrt{A/3}]$ and strictly increasing on $[\sqrt{A/3},\infty[$. It follows from $h(0)<0$ that $h$ is negative on $[0,\sqrt{A/3}[$. Finally $h(\sqrt{A/3})<0$ and $h$ is strictly increasing on $[\sqrt{A/3},\infty[$ and hence has exactly one positive zero we call $F$.
Now define the operator $T(x)=\sqrt{A+B/x}$ for $x>0$. Clearly, $T(F)=F$ and $x<y$ implies $T(x)>T(y)$. In particular, T swaps the intervals $]0,F]$ and $[F,\infty[$. This suggests a study of $T^2:I\to I$, where $I=[F,\infty[$ and $T^2(x)=T(T(x))$.

Claim 2: $T^2(x)<x$ for all $x>F$. By definition, $T^2(x)<x$ is equivalent to $x^2-A>B/T(x)$. Now $x>F$ implies $x^2-A>F^2-A=B/F>0$. Hence $T^2(x)<x$ is equivalent to $(x^2-A)^2(A+B/x)>B^2$ and to $$p(x):=(x^2-A)^2(Ax+B)-B^2x>0\mbox{ for }x>F.$$ By construction, all zeros of $h(x)=x^3-Ax-B$ are zeros of $p$. (For example, $p(F)=0$ because $F^2-A=B/F$ and $AF+B=F^3$.) Hence $h$ must be a factor of $p$. We calculate $$p(x)=(x^3-Ax-B)(Ax^2+Bx-A^2).$$ Now we see that $x>F$ implies $x^3-Ax-B>(F^2-A)F-B=0$ and $Ax^2+Bx-A^2>(AF+B)F-A^2=F^4-A^2>0$ and therefore $p(x)>0$. This proves Claim 2.

Since $F_0<F$ implies $F_1=T(F_0)>F$, it is sufficient to study the convergence of the sequence $(F_n)$ for $F_0>F$. Claim 2 implies that $F_{2n}=T^{2n}(F_0)$ form a decreasing sequence of numbers larger than $F$. Hence they must have a limit, say $\tilde F\geq F$. By the continuity of $T$ we have $T^2(\tilde F)=\tilde F$. This cannot be the case if $\tilde F>F$ because of Claim 2. Therefore $\lim_{n\to\infty} F_{2n}=F$ and by continuity also $\lim_{n\to\infty} F_{2n+1}=\lim_{n\to\infty} T(F_{2n})=T(F)=F$. This proves the convergence of the sequence $F_n$ to $F$ for any initial $F_0>0$.
The estimate $$|T'(F)|=\frac1{2\sqrt{A+B/F}}\frac B{F^2}=\frac B{2F^3}=\frac B{2(AF+B)}<1$$ implies that $F$ is an attractive fixed point of $T$ and hence the convergence of the sequence $F_n$ to $F$ for $F_0$ close to $F$. This is easier to prove than the convergence of the sequence $F_n$ for any initial $F_0$ which we proved above.

$\newcommand{\NN}{{\mathbb{N}}}$ Let us apply the ''standardest approach'' to the second question, but less detailed than above. The result is that different signs of $A,B$ lead to a much more complex situation. If $A,B$ are both positive (or both negative) then convergence of $F_n$, $n\in\NN$, for any initial $F_0$ has been shown. This is the widest range of convergence possible. If $A$ and $B$ have opposite signs, the sequence might terminate at some $F_n=0$, it might not converge even if $F_n$ exist for all $n$ and the behavior depends upon the relation between $A$ and $B$.

Some details: As I prefer dealing with positive $A,B$ let us write the recursion $$F_{n+1}=T(F_n)=\sqrt{|A-B/F|}$$ with $A,B>0$. Obviously $Q=B/A$ plays an important role because $T(x)=\sqrt{\frac Bx-A}$ if $x\in]0,Q]$ and $T(x)=\sqrt{A-\frac Bx}$ if $x\in]Q,\infty]$.

Claim 3: There is a sequence of points $E_n$, $n\in\NN$, such that $T^n(E_n)=0$.

Simply put $E_1=Q$ and $E_{n+1}=\frac B{A+E_n^2}$ for all $n$. Then $T(E_{n+1})=E_n$ etc.

Let us now study the possible limits $F$(=fixed points of $T$).

If $F<Q$, then $F$ satisfies $F^3+AF-B=0$. Easier than for claim 1, it follows that there is exactly one positive solution $F$ which also satisfies $F<Q$. For local convergence, we study $|T'(F)|$ and obtain $|T'(F)|=\frac B{2(B-AF)}$. This is smaller than $1$ iff $2AF<B$ which is equivalent to $AF<B-AF=F^3$, to $F>A^{1/2}$ and finally to $B>2 A^{3/2}$. If $|T'(F)|<1$ then $F_n$ converge to $F$ at least for $F_0$ sufficiently close to $F$.

If $F>Q$ then it satisfies $F^3-AF+B=0$. Now the polynomial $h(x)=x^3-Ax+B$ is positive at $x=0$, decreasing between 0 and $\mu=\sqrt{A/3}$ and then increasing. It has no zero if the minimum $h(\mu)>0$ and two zeros if $h(\mu)<0$. In the first case which is equivalent to $B>\frac 2{3\sqrt3}A^{3/2}$, we have $x^3-Ax+B>0$ for all $x>Q$ and thus $x>\sqrt{A-B/x}=T(x)$ for all $x>Q$. If the initial $F_0>Q$ then $F_n$ decrease until they leave the interval $[Q,\infty[$. In the second case ($h(\mu)<0$), we have $B<\frac 2{3\sqrt3}A^{3/2}$ and hence $Q<\frac23\mu<\mu$: the minimum is reached on $[Q,\infty[$. Furthermore, as $h(Q)=Q^3>0$, both solutions $G<H$ of $x^3-Ax+B=0$ are in $[Q,\infty[$. Contrary to the first part, $Q<x<y$ implies $T(x)<T(y)$ and hence the intervals $[Q,G]$, $[G,H]$, $[H,\infty]$ are stable with respect to $T$ (except for the fact that $T(x)<Q$ is possible for some $x<G$). As in the first case we show that $T(x)<x$ for $x$ in $[Q,G[$ and $]H,\infty]$ whereas $T(x)>x$ on $]G,H[$. Therefore $H$ is an attractive, $G$ a repulsive fixed point.

It is interesting to study what happens to $F_n$ if $B<2 A^{3/2}$ (thus $F$ is unstable) and $B>\frac 2{3\sqrt3}A^{3/2}$ ($G,H$ do not exist, $F$ is the only fixed point of $T$). If we start at some point $F_0\not\in\{E_n,n\in\NN\}$ then $F_n$ exist for all $n$, but cannot converge to any limit. The sequence will probably behave quite chaotic...

This study is, of course, not complete, but it shows that the first questions has a much nicer answer than the second one.

Answer 3

In this case, a sketch is very worthy.

It is clear how the recurrence is graphed, and how it is developing out.

We consider only the domain $0<x$.
In this function has an horizontal asymptote $y_{\infty}= \sqrt{A}$, and remains above that.
The derivative $$ y'(x) = {d \over {dx}}\sqrt {A + B/x} = - \;{B \over {2x^{\,2} \sqrt {A + B/x} }} $$ is always negative if $0<B$.
The second derivative is always positive, for positive $A$ and $B$.

Then, since in the recursion remains $A<x$, if the absolute value of the derivative at $x=\sqrt{A}$ is less than $1$ $$ \left| {y'(\sqrt A )} \right| = \;{B \over {2A\sqrt {A + B/\sqrt A } }} < 1 $$ the Priciple of Contraction guarantees that the recurrence is convergent to $x=y(x)$.