Is this sequence $x_{n+1}=1+\frac{a-1}{1+x_n},$ with $a>1, x_1>0$, convergent or divergent? My question: Assume $$a>1, x_1>0, x_{n+1}=1+\frac{a-1}{1+x_n}.$$ Is this sequence $\{x_n\}_{n=1}^{\infty}$ convergent or divergent as $n\to\infty$? If it is convergent, give a proof (in this case, the limit is obviously $\sqrt{a}$ ). 
This question comes out of the Exercise 1.13, on Apostol's textbook Mathematical Analysis, page 26.  The exercise is:  Let $a$ and $b$ be positive integers. Prove that $\sqrt{2}$ always lies between the two fractions $a/b$ and $(a+2b)/(a+b).$ Which fraction is closer to $\sqrt{2}?$
I have finished this exercise, then I want to construct a algorithm, based on this exercise, to estimate the square root of $a.$  I have tried, but was heavily stuck. Obviously, it is not monotonic, although its even subsequence $\{x_{2k}\}_{k=1}^{\infty}$ and odd subsequence $\{x_{2k-1}\}_{k=1}^{\infty}$ may be monotonic. But I can not prove my guess.  Can anyone help me? 
 A: Big hint of the day


*

*Mathematics is about generalizing ideas, and making connection. You should look at the problem you wish to solve, and the one before it (aka Exercise 1.13), do you see any similarity? If you don't, please read forwards, and when you have reached the end, come back to think about it.

*Notice that in your proof of Exercise 1.13, you don't need the fact that $a$, and $b$ are both positive integer, in fact, they only need to be any positive real numbers.

*Try to generalize the problem, i.e, try to prove that: Given $a, b$ be positive real numbers, and $n$ be any natural number, then $\sqrt{n}$ will always lie between $\dfrac{a}{b}$, and $\dfrac{a + nb}{a+b} = 1 + \dfrac{n-1}{a+b}$, and which is nearer to $\sqrt{n}$?

*Now, prove by induction that, since $x_1 >0$, you will, in fact, have that $x_n > 0,\forall n$

*Fix any natural number $n$, since $x_n > 0$, we can rewrite it as: $x_n = \dfrac{\alpha}{\beta}$, where $\alpha, \beta > 0$ arcording to the formula: $x_{n+1} = 1+\dfrac{a}{1+x_n}$, can you calculate $x_{n+1}$ in terms of $a, \alpha$, and $\beta$? Using the result in number 2 (there are 2 conclusions you can draw from number 2, and the latter is pretty important), what can you say about this sequence?
Regards,
A: The recursion map
$$T:\quad x\mapsto 1+{a-1\over 1+x}={x+a\over x+1}$$
is a Moebius transformation with the two fixed points $\pm\sqrt{a}$. Therefore we introduce a new coordinate function $y$ for which these fixed points are at $0$ and $\infty$. This is accomplished by putting
$$y={x-\sqrt{a}\over x+\sqrt{a}}\ .$$
We then obtain
$$y_{n+1}={x_{n+1}-\sqrt{a}\over x_{n+1}+\sqrt{a}}={{x_n+a\over x_n+1}-\sqrt{a}\over {x_n+a\over x_n+1}+\sqrt{a}}=\ldots=-y_n{\sqrt{a}-1\over\sqrt{a}+1}\ .$$
As $a>1$ it follows that $0<{\sqrt{a}-1\over\sqrt{a}+1}<1$, whence $\lim_{n\to\infty} y_n=0\ $ (or $\lim_{n\to\infty} x_n=\sqrt{a}$) unless the starting point happened to be $y=\infty$, which corresponds to $x=-\sqrt{a}$.
A: Define the sequence $u_{n+1} = a\frac{u_n+1}{u_n+a}$ with $u_1=0$. Using induction it is easy to show that $u_n$ is an increasing sequence that tends to $\sqrt{a}$ as $n\to\infty$. Again using a simple induction we can show that 
$$\forall n\quad u_n < x_n <\frac{a}{u_n}.$$ 
Therefore,
$$\sqrt{a}=\lim _{n\to\infty}u_n\leq \lim _{n\to\infty}x_n\leq \lim _{n\to\infty}\frac{a}{u_n}=\frac{a}{\sqrt{a}}=\sqrt{a}.$$
