How can I deal with recurrent sequences?

Question

I have to find a lot of different limits of recurrent sequences. But I have no idea how to prove existence of limits. I understand that I need to show that sequence is monotonic and bounded. But I have big troubles here. I am trying to use induction but it does not help me. For example, $$x_1>0, a>0, x_{n+1}=\frac{1}{2}(x_n+\frac{a}{x_n})$$

Answer 1

I will use the particular example where $a=2$. The general case will not be difficult to figure out afterward. Assume $x_1=2$.

Consider $x_{n+1}^2-2 = \frac{1}{4}(x_n^2+4+\frac{4}{x_n^2})-2=\frac{x_n^2}{2}+\frac{1}{x_n^2}-1=(\frac{x_n}{2}-\frac{1}{x_n})^2 \geq 0$. This means that the sequence is bounded below by $\sqrt{2}$.

So, consider $x_n-x_{n+1}=x_n-\frac{x_n}{2}-\frac{1}{x_n}=\frac{x_n}{2}-\frac{1}{x_n}=\frac{x_n^2-2}{2x_n} \geq 0$. Thus, our sequence is decreasing.

The monotone convergence theorem then yields that $(x_n)$ converges to some limit in the real line, call it x. Since $(x_{n+1})$ must converge to the same limit, we have $x=\frac{x}{2}+\frac{1}{x}$. So, solving for positive x, we get $x=\sqrt{2}$.

I hope the general case $(a>0)$ is clear from this particular example.

I would also like to note that if you have a hunch for a limit (in this example, $\sqrt{2})$ then the problem tends to be easier since you may have a particular limit in mind. In this case, I figured the limit was $\sqrt{2}$ from the equation in the last line. I used that hunch to show that the sequence was decreasing (since we started at 2 and worked down to $\sqrt{2}$) and that it was bounded below.

Answer 2

By the AM-GM inequality we have $$ x_{n+1} = \frac{1}{2} \left( x_n + \frac{a}{x_n} \right) \ge \sqrt{x_n \frac{a}{x_n} } = \sqrt{a} $$ So this seems to be an instance of Newton's method for $$ f(x) = x^2 - a \\ f'(x) = 2x $$ and indeed $$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n^2 - a}{2x_n} = \frac{x_n^2+a}{2x_n} = \frac{1}{2}\left( x_n + \frac{a}{x_n} \right) $$ This would allow to apply the proof of convergence for Newton's method here.