Given a recurrence relation:
$$
x_{n+1} = b + {a\over x_n} \\
x_1 > 0 \\
a, b > 0 \\
n\in \Bbb N
$$
Prove $\{x_n\}$ converges and find its limit.
First of all notice that $\forall n\in\Bbb N: x_n > 0$. To show the sequence converges it suffices to show it is bounded and monotonic. In case the limit exists then it must equal to one of the fixed points of the recurrence:
$$
x = b + {a\over x} \\
x^2 = bx + a \\
x^2 – bx -a = 0
$$
So the roots are given by:
$$
x = \frac{b \pm \sqrt{b^2 + 4a}}{2}
$$
Since $x_n > 0$ the only possible fixed point is:
$$
x = \frac{b + \sqrt{b^2 + 4a}}{2}
$$
The whole sequence doesn't seem like a monotone one. But it contains monotone subsequences.
So apparently one has to consider two subsequences $x_{2k}$ and $x_{2k-1}$, then show both of them converge by monotone convergence theorem and then show the limits are equal, which would imply the convergence of $x_n$.
I've evaluated $x_{n+2}$ as:
$$
x_{n+2} = {a\over x_{n+1}} + b = {a\over {{a\over x_{n}} + b}} + b \\
= \frac{ax_n + ab + b^2 x_n}{a+bx_n}
$$
Now I wan't to show:
$$
m \le x_{2k+2} \le x_{2k}
$$
Or:
$$
M \ge x_{2k+2} \ge x_{2k}
$$
which seems to be dependent on the initial conditions.
Where $m$ and $M$ are bounds to be found (are they just equal to the fixed point?). The same is related to odd terms of the sequence. Unfortunately I haven't been able to prove monotonicity of $x_{2k}$ and $x_{2k-1}$. How do I proceed from here?
Also please note this problem is given before the definition of a derivative. So the instrumentation is constrained accordingly.
Thank you!
Best Answer
Let $M=\frac{b+\sqrt{b^{2}+4a}}{2}$ and suppose $x_{n}>M$. Then $b+\frac{a}{x_{n}}<b+\frac{a}{M}=M$, so $x_{n+1}<M$ and in the same way $b+\frac{a}{x_{n+1}}>b+\frac{a}{M}=M$ so $x_{n+2}>M$. Thus the elements of the sequence $(x_{n})$ are alternating larger and smaller than $M$.
Now note that $x_{n}^{2}-bx_{n}-a>0$. Thus we find $$x_{n+2}-x_{n}=\frac{ax_{n}+ab+b^{2}x_{n}}{a+bx_{n}}-x_{n}=\frac{ab+b^{2}x_{n}-bx_{n}^{2}}{a+bx_{n}}=b\frac{a+bx_{n}-x_{n}^{2}}{a+bx_{n}}.$$ As $b>0$, $a+bx_{n}>0$ and $a+bx_{n}-x_{n}^{2}<0$ we find that $x_{n+2}-x_{n}<0$ and hence $M<x_{n+2}<x_{n}$.
We can use a similar argument for $0<x_{n}<M$ using $x_{n}^{2}-bx_{n}-a<0$ to show that $x_{n}<x_{n+2}<M$. Taking wlog $0<x_{1}<M$ we find that $(x_{2n+1})$ and $(x_{2n})$ are both respectively monotonically increasing and monotonically decreasing bounded sequences converging respectively to some $0<L_{1}\leq M\leq L_{2}$.
Finally suppose $L_{1}\neq M$. Then $$0=\lim_{n\rightarrow\infty}x_{2n+3}-x_{2n+1}=b\frac{a+bx_{2n+1}-x_{2n+1}^{2}}{a+bx_{2n+1}}=b\frac{a+bL_{1}-L_{1}^{2}}{a+bL_{1}}$$ which we know holds only if $L_{1}=M$ as $b>0$ and $a+bL_{1}>0$, which is a contradiction. One can rule out $L_{2}\neq M$ similarly.