2

I want to prove that the sequence defined by $\{x_1=1,\,x_{n+1}=\frac {x_n}2+\frac 1{x_n} \}$ has a limit.

By evaluating the sequence I notice that the sequence is strictly monotonically decreasing starting from $x_2=1.5$.

It seems to suggest itself to prove that the sequenced is bounded by $1\le\big( x_n \big)_{n\ge1} \le 1.5$ and to prove that it is strictly monotonically decreasing starting at $x_2$ which would imply convergence.

How would I proceed and could one prove the existence of the limit without first evaluating the values of the sequence to see how the sequence behaves?

gbag
  • 497
  • I'm not sure if this constitutes a proof, but you can observe that your recurrence relation is equivalent to the one given by Newton's method for finding a root of $x^2-2$, which converges to $\pm\sqrt{2}$. – David Zhang Aug 04 '13 at 22:56
  • Linking a few closely related questions: 1, 2, 3. – Frenzy Li Jul 06 '17 at 03:05

4 Answers4

3

This is the method used in Example 3.3.5 of Introduction to Real Analysis, Bartle and Sherbert:

You could first show that $(x_n)$ is bounded below by $\sqrt2$, for $n>1$: Note that $x_n$ satisfies the quadratic equation $x_n^2-2x_n x_{n+1}+2=0$. So this equation has a real root. Its discriminant $4x_{n+1}^2-4\cdot2$ is nonnegative.

Then show $(x_n)$ is decreasing. Towards this end, use the above and write $$ x_n-x_{n+1}= x_n-{1\over 2}\Bigl(x_n+{2\over x_n}\Bigr)={1\over 2}{(x_n^2-2)\over x_n}\ge 0. $$

It follows that $(x_n)$ converges. To find the limit, $L$, take the limit of both sides of $$x_{n+1}={x_n\over 2}+{1\over x_n}$$ and solve for $L$.

Though explicitly evaluating various $x_n$ is helpful and gives intuition towards solving the problem, there is no need to do so.

David Mitra
  • 74,748
  • How did you transform $x_n-{1\over 2}\Bigl(x_n+{2\over x_n}\Bigr)$ into ${1\over 2}{(x_n^2-2)\over x_n}$? – gbag Jun 10 '13 at 12:06
  • 3
    @gbag $$ x_n-{1\over2}\Bigl( x_n+{2\over x_n}\Bigr)=x_n-{x_n\over2}-{1\over x_n}={x_n\over 2}-{1\over x_n}={1\over2}\Bigl(x_n -{2\over x_n}\Bigr)={1\over2}{x_n^2-2\over x_n}.$$ – David Mitra Jun 10 '13 at 12:30
2

A. $x_n>0$ , $n\in \mathbb{N}$.

B. We will show that $\{x_2, x_3, \ldots, x_n, \ldots \}$ is monotonically non-increasing. $$ 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^2_n-2}{2x_n}, \qquad n>1. $$ But $x^2_n-2>0$, when $n>1$, because $$ x^2_n-2 = \left( \dfrac{x_{n-1}}{2}+\dfrac{1}{x_{n-1}} \right)^2 - 2 = \dfrac{x^2_{n-1}}{4} + 1 + \dfrac{1}{x^2_{n-1}} - 2 = $$ $$ \dfrac{x^2_{n-1}}{4} - 1 + \dfrac{1}{x^2_{n-1}} = \left( \dfrac{x_{n-1}}{2}-\dfrac{1}{x_{n-1}} \right)^2 \geqslant 0. $$ So, $$x_n-x_{n+1} \geqslant 0.$$ Proved.

C. Since the sequense has the limit (denote $X$) $-$ as bounded and non-increasing sequence, then

$$ X = \frac{X}{2}+\frac{1}{X}; $$ $$ X^2 = \frac{X^2}{2}+1; $$ $$ \frac{X^2}{2}=1; $$ $$ X = \sqrt{2}. $$

Pedro
  • 122,002
Oleg567
  • 17,295
2

$ \text {Assumption: } \big(x_n\big)_{n\ge2} \text { is strictly monotonically decreasing} \tag{1} \\ $ $ \text {Assumption: } \sqrt2 \le \big(x_n\big)_{n\ge2} \tag{2} $

Strictly monotonic & bounded $\Longrightarrow$ convergent.

$$\begin{align*} \text {ad (1):} && x_{n+1} &< x_n \\ && \frac{x_n}2+\frac 1{x_n} &< x_n \\ && \frac{x_n^2}2+1 &< x_n^2 \\ && 1 &< \frac{x_n^2}2 \\ && 2 &< x_n^2 \\ && \sqrt2 &< x_n \end{align*} $$

If we can prove $\sqrt2<x_n$, then both $(1)$ and $(2)$ hold and the convergence is proven.

$$\begin{align*} \text {Induction by } n \\ n=2\text : & \sqrt2 < 1.5 = x_2 \\ n\to n+1\text : & \text {Assume } \sqrt2 < x_n \text{ holds.} \\ & \sqrt2 < x_{n+1} \\ & \sqrt2 < \frac {x_n}2+\frac1{x_n}=\frac{x_n^2+2}{2x_n} \\ & \text{By assumption } x_n=\sqrt2+\delta \text{ for a positive } \delta. \\ & \sqrt2 < \frac{\left( \sqrt2+\delta \right)^2+2}{2\left( \sqrt2+\delta \right)} \\ & 4+2\sqrt2\delta < \left( \sqrt2+\delta \right)^2+2 \\ & 2+2\sqrt2\delta<2+2\sqrt2\delta+\delta^2 \\ & 0 < \delta^2 & \square \\ \end{align*} $$

gbag
  • 497
2

Firstly, it is clear that $x_n>0$ for all $n \in \mathbb N$.

Secondly, the AM-GM inequality states that $x_{n+1}=\frac{x_n}{2}+\frac{1}{x_n} \geq 2 \cdot \sqrt{\frac{1}{2}}=\sqrt{2}$.

Lastly, according to the last result, for $n \geq 2$, $\frac{x_{n+1}}{x_n}=\frac{1}{2}+\frac{1}{x_n^2} \leq 1$, so that $x_{n+1} \leq x_n$.

We have shown that the sequence $(x_n)$ is bounded and eventually monotonic, thus it has a limit according to the monotone convergence theorem.

user1337
  • 24,381