Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Define the sequence $\{x_n\}_{n\in\mathbb{N}}$ by $$x_0=\frac{M}{2}, \qquad x_{n+1}=\frac{1}{2}\left(x_{n}+\frac{M}{x_{n}}\right)$$ where $M\in\mathbb{R}$, $M\geq 0$. Find $\lim\limits_{x_n\to\infty}x_{n}$ and prove it exists.

My idea was, if I can prove that $x_{n}\geq x_{n+1}$ then I can say that

$$x_{n}\geq x_{n+1}\iff x_{n}\geq\dfrac{1}{2}\left(x_{n}+\dfrac{M}{x_{n}}\right)\iff 2x_{n}\geq x_{n}+\dfrac{M}{x_{n}}\iff$$ $$ x_{n}\geq\frac{M}{x_{n}}\Longleftrightarrow x_{n}^{2}\geq M\Longleftrightarrow x_{n}\geq\sqrt{M}$$

but I couldn't find a way to prove that $x_{n}\geq x_{n+1}$.

share|improve this question
    
Do you want $x_0=M/2$ and $M\ge0$? –  David Mitra Jan 17 '12 at 22:06
    
i'm not sure about $x_0=n/2$. are you using $n$ in different ways? maybe you want $M/2$ or something else (besides zero)? –  yoyo Jan 17 '12 at 22:08
    
oops yeah, I mean M/2 –  sony jimbo Jan 17 '12 at 22:12

4 Answers 4

up vote 4 down vote accepted

Assuming that $M>0$:

First we show that $(x_n)$ is bounded below:

Note $x_n$ satisfies $x_n^2-2x_{n+1}x_n+M=0$. This quadratic has a real root, so $4x_{n+1}^2-4M\ge 0$.

So $x_{n+1}^2\ge M$.

Next, we show that $(x_n)$ is eventually decreasing:

For $n\ge 2$ $$x_n-x_{n+1}=x_n-{1\over2}\Bigl(x_n+{M\over x_n}\Bigr)={1\over2}{x_n^2-M\over x_n}\ge 0$$

Thus, since $(x_n)$ is bounded below by $\sqrt M$ and is eventually decreasing, $(x_n)$ converges to some $L$ with $L\ge \sqrt M>0$. But then $$ x_{n+1}\rightarrow{1\over2}\Bigl( L+{M\over L}\Bigr). $$

We then must have $$ L={1\over2}\Bigl( L+{M\over L}\Bigr); $$ which implies $L=\sqrt M$.

If $M=0$, then $(x_n)$ obviously converges to 0.

share|improve this answer
    
+1: Interesting proof of $x_{n+1} \ge \sqrt{M}$. An easier proof (which generalizes to $k^{th}$ roots) uses $\text{AM} \ge \text{GM}$, see: math.stackexchange.com/questions/82682/… –  Aryabhata Feb 2 '12 at 2:02

For any positive $M$, this method seems to converge and is decreasing towards a solution after the first iteration (for $x_0 > 2$, it is always decreasing, but for $x_0 < 2$, it takes one iteration to increase and then decreases towards the solution. I'll explain that below). To have $x_n \ge x_{n+1}$, you need $$ x_n \ge x_{n+1} = \frac 12 \left( x_n + \frac M{x_n} \right) \qquad \Longleftrightarrow \qquad x_n^2 - M \ge 0 \qquad \Longleftrightarrow \qquad x_n \ge \sqrt M $$ if we assume that $x_0$ is positive to begin with. (Otherwise, one can prove that a convergent sequence following this pattern will be a root of $x^2 - M$ with $M$ negative, which means that the root $x$ would be complex, which is not what you expect I assume). We show further that $x_n \ge x_{n+1} \ge M$. Now we can see that \begin{align} x_n^2 - 2 \sqrt M x_n + M = (x_n-\sqrt M)^2 \ge 0 \quad & \Longrightarrow \quad x_n + \frac{M}{x_n} \ge 2 \sqrt M \\ & \Longrightarrow \quad \frac 12 \left( x_n + \frac {M}{x_n} \right) \ge \sqrt M \\ \end{align} and therefore we know that after the first iteration, $x_n$ will always be above $\sqrt M$, since the only thing I assumed here was that $x_0$ was positive (strict).

Therefore the sequence is converging because it decreases and it is bounded below by $\sqrt M$. To find the limit, we have $$ x_n \to L \qquad \Longrightarrow \qquad x_{n+1} \to L = \frac 12 \left( L + \frac ML \right) \qquad \Longrightarrow \qquad L = \sqrt M $$ by knowing the limit has to be positive (you'll find a quadratic with two roots in there).

To explain the first iteration thing, you have to note that $$ x_0 = \frac M2 \ge \sqrt M \qquad \Longleftrightarrow \qquad (\sqrt M)^2 - 2 \sqrt M \ge 0 $$ which in turn is equivalent to $\sqrt M \ge 2$, which means $M \ge 4$ and $x_0 \ge 2$. Hope that helps,

share|improve this answer

if the limit $x$ exists, then $x=(1/2)(x+M/x)$ and $x=\pm\sqrt{M}$. see newton's method applied to $f(x)=x^2-M$

share|improve this answer
    
sorry forgot to mention that we don't know if the limit xn exists –  sony jimbo Jan 17 '12 at 22:03

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{x_{0}\equiv{M \over 2},\quad x_{n+1}\equiv\half\,\pars{x_{n} + {M \over x_{n}}}.\qquad M \geq 0.}$

Let's $\ds{y_{n} = {x_{n} \over \root{M}}\quad\imp\quad y_{n + 1} = \half\pars{y_{n} + {1 \over y_{n}}}\,,\quad y_{0} = {\root{M} \over 2}}$ \begin{align} {y_{n + 1} + 1 \over y_{n + 1} - 1}& ={\half\pars{y_{n} + 1/y_{n}} + 1 \over \half\pars{y_{n} + 1/y_{n}} - 1} ={y_{n}^{2} + 2y_{n} + 1 \over y_{n}^{2} - 2y_{n} + 1} =\pars{y_{n} + 1 \over y_{n} - 1}^{2} \end{align}

\begin{align} {y_{n + 1} + 1 \over y_{n + 1} - 1}& =\pars{y_{n - 1} + 1 \over y_{n - 1} - 1}^{4} =\pars{y_{n - 2} + 1 \over y_{n - 2} - 1}^{8}=\cdots =\pars{y_{0} + 1 \over y_{0} - 1}^{2^{n + 1}} \end{align}

$$ y_{n + 1} = {\pars{y_{0} + 1}^{2^{n + 1}} + \pars{y_{0} - 1}^{2^{n + 1}} \over \pars{y_{0} + 1}^{2^{n + 1}} - \pars{y_{0} - 1}^{2^{n + 1}}} $$ Now, you can take from here.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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