Let $a>0$ and $x_1>0$. Define the sequence $(x_n)$ recursively as $$x_n=\frac{1}{2}\left(x_{n-1}+\frac{a}{x_{n-1}}\right) \tag{1}$$

We have to show that $x_n$ is convergent and find the limit. I know that there is a way of considering the given formula as a quadratic equation in $x_n$ and then using the fact that the discriminant is non-negative. But I want to achieve a direct proof.

Firs of all, it is clear from the definition that all the terms of the sequence is strictly positive. Playing around with the sequence a bit, it became clear to me that if $x_1<\sqrt{a}$ then it increases until it overtakes $\sqrt{a}$, then decreases until it goes under $\sqrt{a}$, and so on. If it touches $\sqrt{a}$ at any point then it becomes a constant sequence after that point, each consequent term being $\sqrt{a}$. Thus, an obvious target for the limit is $\sqrt{a}$.

Hence, we consider estimating the quantity $$|x_n-\sqrt{a}|$$

Using $(1)$, we obtain $$|x_n-\sqrt{a}|=\left|\frac{1}{2}\left(x_{n-1}+\frac{a}{x_{n-1}}\right)-\sqrt{a}\right|=\frac{|x_{n-1}-\sqrt{a}|^2}{2x_{n-1}} \tag{2}$$

The temptation is to apply $(2)$ repetitively to obtain something like

$$|x_n-\sqrt{a}|=\frac{|x_{1}-\sqrt{a}|^{\text{something big}}}{(2x_{n-1})(2x_{n-2})^2 \cdots}$$

I have two problems here. We have to show that $(x_n)$ safely bounded away from $0$ so we can bound the terms in the denominator (which I think should be do-able). The more crucial part is that we cannot assume $|x_1-\sqrt{a}|<1$. So we gotta look for some $N$ such that $|x_N-\sqrt{a}|<1$.

Any help to complete this $``$direct$"$ proof will be much appreciated. Thank you.

marked as duplicate by Professor Vector, Brian Borchers, The Phenotype, BCLC, Martin R Mar 8 at 15:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • @ProfessorVector You're right. Thanks for the information. It's difficult to search for these duplicates for particular problems. I'll still keep the post as I discussed about a specific approach to solve the problem. I think someone can join the final dots. – Samayita Mar 8 at 14:40
up vote 2 down vote accepted

First, by induction, prove that $x_n > 0$, for all $n$.

Next, for all $n > 1$, applying $\text{AM}$-$\text{GM}$, \begin{align*} &x_n = \frac{1}{2}\left(x_{n-1}+\frac{a}{x_{n-1}}\right)\\[4pt] \implies\;&x_n > \sqrt{a}\\[4pt] \end{align*} Next, note that for $n > 2$, \begin{align*} &x_n = \frac{1}{2}\left(x_{n-1}+\frac{a}{x_{n-1}}\right)\\[4pt] \implies\;&2x_n = x_{n-1}+\frac{a}{x_{n-1}}\\[4pt] \implies\;&2(x_n - x_{n-1}) = \frac{a}{x_{n-1}}-x_{n-1}\\[4pt] \implies\;&2(x_n - x_{n-1}) < \frac{a}{\sqrt{a}}-\sqrt{a}\\[4pt] \implies\;&2(x_n - x_{n-1}) < 0\\[4pt] \end{align*} Thus, for $n > 1$, the sequence $(x_n)$ is strictly decreasing.

Since for $n > 1$, the sequence $(x_n)$ is bounded below by $\sqrt{a}$, it follows by the monotone convergence theorem for real numbers that $(x_n)$ must approach a limit, $c$ say, with $c \ge \sqrt{a}$.

Taking limits on both sides of the recursion, we get $$c={\small{\frac{1}{2}}}\left(c+\frac{a}{c}\right)$$ Solving for $c$, and rejecting the negative root, we get $c=\sqrt{a}$.

Remarks:

Checking for positivity, checking for bounds, checking for monotonicity; those should be considered as key goals in the initial exploration of the problem. In this case, those goals were readily achieved, and the problem resolved very naturally.

  • 1
    Smooth. Thanks a lot. – Samayita Mar 8 at 15:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.