13
$\begingroup$

a) Let $a>0$ and the sequence $x_n$ fulfills $x_1>0$ and $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$ for $n \in \mathbb N$. Show that $x_n \rightarrow \sqrt a$ when $n\rightarrow \infty$.

I have done it in two ways, but I guess I'm not allowed to use the first one and the second one is incomplete. Can someone please help me?

  1. We already know $x_n \rightarrow \sqrt a$, so we do another step of the iteration and see that $x_{n+1} = \sqrt a$.

  2. Using limit, $x_n \rightarrow x, x_{n+1} \rightarrow x$ (this is the part I think it's incomplete, don't I have to show $x_{n+1} \rightarrow x$, how?), we have that

$$x = \frac x 2 (1 + \frac a {x^2}) \Rightarrow 1 = a/x^2 \Rightarrow x = \sqrt a$$

b) Let the sequence $x_n$ be defined as $x_{n+1}= 1 + \frac 1 {x_n} (n \in \mathbb N), x_1=1$. Show that it converges and calculate it's limit.

"Tip: Show that sequences $x_{2n}$ and $x_{2n+1}$ monotone convergent to the limit." I didn't understand the tip, how can this help me? Does it make a difference if the number is odd or even?

Thanks in advance!

  • 1
    This link might be useful for a: http://www.proofwiki.org/wiki/Iterative_Process_for_Estimating_Square_Roots2011-11-17
  • 0
    oops martin, sorry, you're right!2011-11-17
  • 0
    When you (or someone) cleverly noticed that $x_n=\frac{F_{n+1}}{F_n}$, where $F_n$ is the $n$-th term of Fibonacci sequence, you could use show this by induction. Then you can find $x_{n+1}-x_n=\frac{F_{n+2}}{F_{n+1}}-\frac{F_{n+1}}{F_n}=\frac{F_nF_{n+2}-F_{n+1}}{F_nF_{n+1}}=(-1)^{n+1}\frac1{F_nF_{n+1}}$, using [Cassini's identity](http://www.proofwiki.org/wiki/Cassini%27s_Identity). This means that the sequence is alternating and that $\frac1{|x_n-x_{n+1}|}\to0$. \\ This is basically the suggestions from Aryabhata's answer.2011-11-17

7 Answers 7

15

(a) Yes, you need to show first that $\langle x_n\rangle_n$ is convergent; once you know that, your argument shows that its limit must be $\sqrt a$. You might want to look first at the discussion below for (b).

(b) Yes, it does make a difference whether $n$ is odd or even. Calculate the first few values: $$x_1=1, x_2 = 2,x_3=\frac32,x_4=\frac53,x_5=\frac85,x_6=\frac{13}8.$$ Note that the sequence is oscillating: the odd-numbered terms are low, and the even-numbered terms are high. On the other hand, $x_1x_4>x_6$. This suggests that the sequence does converge to some limit $x$ in such a way that $$x_1

If you can show that $x_{2n+1}

(By the way, the terms of this sequence are the ratios of consecutive Fibonacci numbers, and their limit is $\varphi = \frac12(1+\sqrt 5)$.)

Added: After some algebra we get $$x_{n+2}=1+\frac1{x_{n+1}}=1+\left(1+\frac1{x_n}\right)^{-1}=\frac{2x_n+1}{x_n+1}$$ and $$x_{n+4}=\frac{5x_n+3}{3x_n+2}\;.$$ Thus,

$$\begin{align*} x_{n+4}

Since $x_4=\frac53<2=x_2$, it follows by induction from $(1)$ that $\langle x_{2n}:n\in\mathbb{Z}^+\rangle$ is a decreasing sequence. The calculation in $(1)$ remains valid if all of the inequalities are turned around, and $x_3=\frac32>1=x_1$, so essentially the same induction shows that $\langle x_{2n-1}:n\in\mathbb{Z}^+\rangle$ is a decreasing sequence.

Now let $\varphi=\frac12(1+\sqrt 5)$, the positive zero of $x^2-x-1$. Note that if $x$ is a positive real number, $x>\varphi$ iff $x^2-x-1>0$. Moreover,

$$\begin{align*} x_{n+2}^2-x_{n+2}-1&=\left(\frac{2x_n+1}{x_n+1}\right)^2-\frac{2x_n+1}{x_n+1}-1\\ &=\frac{x_n^2-x_n-1}{(x_n+1)^2}\;, \end{align*}$$

and $(x_n+1)^2>0$, so $x_{n+2}^2-x_{n+2}-1$ and $x_n^2-x_n-1$ have the same algebraic sign, and therefore $x_{n+2}>\varphi$ iff $x_n>\varphi$. Now $\varphi\approx 1.618$, so $x_2>\varphi$, and it follows by induction that $x_{2n}>\varphi$ for every $n\in\mathbb{Z}^+$.

Similarly, $x<\varphi$ iff $x^2-x-1<0$ if $x$ is a positive real, and $x_1=1<\varphi$, so the same induction shows that $x_{2n-1}<\varphi$ for every $n\in\mathbb{Z}^+$. Thus, $$x_1same limit, but we’re getting there.

There are several ways to finish the job. One is to let $L$ be the limit of one of the subsequences, say the even-numbered one. Then $$L=\lim_{n\to\infty}x_{2n+2}=\lim_{n\to\infty}\frac{2x_{2n}+1}{x_{2n}+1}=\frac{2L+1}{L+1}\;,$$ so $L^2+L=2L+1$, $L^2-L-1=0$, and $L=\varphi$ (since the negative solution is plainly wrong). A similar calculation takes care of the other subsequence.

Another approach is to consider $$\left|\frac{x_{n+2}-x_{n+1}}{x_{n+1}-x_n}\right|=\left|\frac{\frac{5x_n+3}{3x_n+2}-\frac{2x_n+1}{x_n+1}}{\frac{2x_n+1}{x_n+1}-x_n}\right|=\left|\frac1{3x_n+2}\right|=\frac1{3x_n+2}<\frac12,$$ since the $x_n$ are all positive. In other words, the gap between consecutive terms shrinks at least geometrically and therefore tends to $0$, so the two subsequences must actually have the same limit, and it must satisfy $L=\frac1{L+1}$.

  • 0
    hi brian, thanks for the reply. I think I have to prove this with induction, but I'm lost as to which step to do or what the beginning of the induction is. any tips?2011-11-16
  • 0
    @Clash: Induction looks good. Note that $x_{n+2}=1+\frac1{x_{n+1}}=1+\left(1+\frac1{x_n}\right)^{-1}=$ $1+\frac{x_n}{x_n+1}=\frac{2x_n+1}{x_n+1}$. When is $\frac{2x_n+1}{x_n+1}x_n$? What is $x_{n+4}$ in terms of $x_n$? Try using this to show that if $x_{n+2}$.2011-11-16
  • 0
    Brian, I swear I'm trying to solve it since I posted. I just can't move forward. All I got was $x_{n+2} > x_n$, when $x_n^2 < x_n + 1$. As all the values are contained in [1, 2], I guess this does make some sense. I then reached your answer at $\varphi$. I suppose I'm trying to solve it with the wrong tools.2011-11-16
  • 0
    So, $x_{n+2} > x_n$ until $x_n < \varphi = \frac12(1+\sqrt 5)$?2011-11-16
  • 1
    @Clash: With a bit of algebra you get $x_{n+4}=\frac{5x_n+3}{3x_n+2}$, which is $>\frac{2x_n+1}{x_n+1}$ iff $x_n^2-x_n-1<0$, which is exactly the condition that you found was equivalent to $x_{n+2}>x_n$. Thus, $x_{n+4}>x_{n+2}$ iff $x_{n+2}>x_n$; since $x_12011-11-16
  • 0
    Hi Brian! Thanks for the great answer. I think I'm almost there. I did have your $x_{n+4}$, just didn't understand the relation. Thanks for clearing that up! I now have $x_{n+3}=\frac{3x_n+2}{2x_n+1}$ and $x_{n+5}=\frac{13x_n+8}{8x_n+5}$, which are both $$x_n=x_{n+1}$ (since both converge) and get $\varphi$? Thanks a lot in advance! – 2011-11-17
  • 0
    wait, I didn't have to had to calculate $x_{n+3}$ and $x_{n+5}$, right? I could have just showed that $x_{n+4}0$. Is this right?2011-11-17
  • 0
    (sorry for the third comment in a row). I mean, if I have shown it's monotone and lower/upper bounded, I can write $x_{n+1}=x_n$, right? Then I'd get $\varphi = \frac12(1+\sqrt 5)$. btw small mistake, $x_{n+5}$ is actually $\frac{8x_n+5}{5x_n+3}$.2011-11-17
  • 0
    @Clash: Rather than respond in detail in the comments, I’ve gone ahead and completed the solution in the answer proper; you’ve clearly put thought into it at this point.2011-11-18
  • 0
    sadly I had to finish my exercise before I saw your reply, but wow! Thanks a lot, now it's 100% clear to me!2011-11-21
  • 0
    You are wrong that the sequence oscillates around $a$. AM/GM means that all $x_i$ are the average of two terms whose Geometric Mean is $\sqrt a$, so $x_i>\sqrt a$ for all $i>1$.2015-09-21
11

(a) Your argument shows that, if the sequence ($x_n$) converges, its limit must be $\sqrt{a}$. To show it in fact converges to $\sqrt{a}$, we note that

$$\begin{align*}x_{n+1}-\sqrt{a} &=\frac12\left(x_n-\sqrt{a}+\frac{a}{x_n}-\sqrt{a}\right)\\ &=\frac12\left(1-\frac{\sqrt{a}}{x_n}\right)\left(x_n-\sqrt{a}\right)\\ &=\frac1{2x_n}(x_n-\sqrt{a})^2. \end{align*}$$

Since we can show (by induction) that $x_n>0$ and $x_{n+1}\ge\sqrt{a}\ $ (for $n\ge 1$), we have

$$|x_{n+1}-\sqrt{a}|=\frac12\left|1-\frac{\sqrt{a}}{x_n}\right||x_n-\sqrt{a}|\le\frac12|x_n-\sqrt{a}|.\quad (n\ge 2)$$

Therefore $0\le |x_n-\sqrt{a}|\le \left(\frac12\right)^{n-2}|x_2-\sqrt{a}|$, and by the squeeze theorem we obtain $|x_n-\sqrt{a}|\to 0$.

(b) A similar argument can be used to show that, if the sequence ($x_n$) converges, its limit $\alpha$ must satisfy $\alpha=1+\frac1{\alpha}$. Since we can show (by induction) $x_n>0$, $\alpha=\frac{1+\sqrt5}{2}$, not $\frac{1-\sqrt5}{2}$.

To show that it in fact converges to $\alpha$, we note that $$\begin{align*} x_{n+1}-\alpha=\frac1{x_n}-\frac1{\alpha}=-\frac{1}{\alpha x_n}(x_n-\alpha). \end{align*}$$

Since we can show (by induction) that $x_n\ge 1$, we have

$$|x_{n+1}-\alpha|=\left|\frac1{\alpha x_n}\right||x_n-\alpha|\le \frac1{\alpha}|x_n-\alpha|\quad \text{with}\quad 0<\frac1{\alpha}<1.$$

Therefore $0\le |x_n-\alpha|\le \left(\frac1\alpha\right)^{n-1}|x_1-\alpha|$, and by the squeeze theorem we obtain $|x_n-\alpha|\to 0$.

(P.S. It is true that "$x_{2n}$ and $x_{2n+1}$ are monotone convergent to the limit", but it is not necessary to show it here.)

4

Extended from this answer to a deleted question.

Note that all $x_n>0$ and $$ x_{n+1}^2=\frac14\left(x_n+\frac{a}{x_n}\right)^2=\frac14\left(x_n-\frac{a}{x_n}\right)^2+a\ge a\tag{1} $$ Thus, all $x_n$ past the first satisfy $x_n^2\ge a$. Therefore, $$ x_{n+1}-x_n=\frac{a-x_n^2}{2x_n}\le0\tag{2} $$ says that $x_{n+1}\le x_n$. Therefore, $\{x_n\}$ is a decreasing sequence, bounded below. Thus, the sequence converges. Furthermore, since the sequence converges, $$ \lim_{n\to\infty}a-x_n^2=\lim_{n\to\infty}2x_n(x_{n+1}-x_n)=0\tag{3} $$ Therefore, $$ \lim_{n\to\infty}x_n^2=a\tag{4} $$

  • 0
    The proof of (4) holds up under the rational numbers.2017-05-21
  • 0
    @MikeMathMan: I am not sure what you mean. Are you saying there is a problem in the answer?2017-05-21
  • 0
    No. I love your proof! Just meant that it even works if your domain of discourse is the rational numbers. What is the motivation /insight for writing down (1)? If standard technique, where else? If original and yours - brilliant!2017-05-21
  • 0
    @robjohn I really like this proof, much better than the others I have seen. I'm stuck with part (3) however, could you please help me understand it?2018-05-23
  • 0
    @Daniele1234: Multiply $x_{n+1}-x_n=\frac{a-x_n^2}{2x_n}$ by $2x_n$.2018-05-23
  • 0
    @robjohn Then how does one conclude limn→∞2xn(xn+1−xn)=02018-05-23
  • 0
    @Daniele1234: the sequence decreases, so $x_n\le x_1$, and the sequence converges, so $x_{n+1}-x_n\to0$.2018-05-23
  • 0
    @robjohn And can one show $x_{n+1}-x_n\to0$ without the Cauchy Criterion (all I know now is MCT and BWT)?2018-05-23
  • 0
    @Daniele1234: it was shown that since $x_n$ is monotonically decreasing and bounded below, $x_n$ converges. This immediately gives that $x_{n+1}-x_n\to0$.2018-05-23
  • 0
    @robjohn I understand that by MCT $x_n$ converges, but to claim that $x_{n+1}-x_n\to0$ is true requires the Cauchy Criterion or am I wrong - can you derive that using only Axiom of Completeness/MCT/etc2018-05-23
  • 0
    @Daniele1234: [a sequence of real numbers which is monotonically decreasing and bounded below is convergent](https://en.wikipedia.org/wiki/Monotone_convergence_theorem#Convergence_of_a_monotone_sequence_of_real_numbers)2018-05-23
  • 0
    @robjohn Yes Monotone Convergence Theorem as I said.... However, why does it being convergent allow you to rigorously claim that $x_{n+1}-x_n\to0$?2018-05-23
  • 0
    @Daniele1234: Consider [the property](https://en.wikipedia.org/wiki/Limit_of_a_sequence#Properties) that $\lim\limits_{n\to\infty}\left(x_{n+1}-x_n\right)=\lim\limits_{n\to\infty}x_{n+1}-\lim\limits_{n\to\infty}x_n$. Alternatively, you could use [the definition](https://en.wikipedia.org/wiki/Limit_of_a_sequence#Formal_definition) and [the triangle inequality](https://en.wikipedia.org/wiki/Triangle_inequality).2018-05-23
3

For a) a simple proof exists and can be generalized to the sequence $$K x_{n+1} = (K-1)x_n + \frac{a}{x_n^{K-1}}$$

which converges to $\sqrt[K]{a}$ (your sequence has $K=2$).

Use $\text{AM} \ge \text{GM}$ to show that

$x_{n+1} \ge \sqrt{a}$.

Now $x_{n+1} - x_n = \frac{a - x_n^2}{2x_n} \le 0$ as $x_n \ge \sqrt{a}$ for $n \gt 1$.

Thus the sequence is monotonically decreasing (starting from $n=2$) and bounded below and so converges.

For b) refer to various proofs here: Why does this process, when iterated, tend towards a certain number? (the golden ratio?)

(The link above applies to $y_n = \frac{1}{x_n}$).

  • 0
    what's AM and GM?2011-11-17
  • 0
    @Clash http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means2011-11-18
0

Following robjohn note that $$x_{n+1} \le x_n$$ and by AM-GM inequality, $$|x_{n+1}|=\frac{1}{2}|x_n+\dfrac{a}{x_n}| \ge \sqrt{x_n.\frac{a}{x_n}}=\sqrt{a}$$ By monotone convergent theorem $\lim_{n \to \infty}x_n=x$ is exist as a real number.
Note that $x^2=a.$

0

For a):

The proof of convergence can be deduced from the question/answer LFT theory found in

Iterative Convergence Formulation for Linear Fractional Transformation with Rational Coefficients

Proof when $x_1^2 > a$

Note: If both $a$ and $x_1$ are rational numbers, then this solution is obtained without recourse to the real number system.

Let $S$ represent $a$ and $K$ denote $x_1$.

We have our LFT theory for

$F(x) = \frac{S + Kx}{K + x}$

as espoused in the above link.

Considering Proposition 2 & 3, we have a sequence

$\{F^1, F^2, F^3, ..., F^n, ...\}$ of LFTs

with the corresponding decreasing sequence of Ks

$\{K, K_2, K_3, ..., K_n, ...\}$ and $(K_n)^2$ converges to $S$.

Might as well set $K_1$ to $K$ now.

Now with a little thought, you can see the following holds:

$K_2 = (S + K_1^2)/2K_1$

$K_4 = (S + K_2^2)/2K_2$

$K_8 = (S + K_4^2)/2K_4$

$K_{16} = (S + K_8^2)/2K_8$

etc.

But this is exactly the Babylonian Method.

So the method can actually be described as calculating numbers that are a subsequence of our convergent sequence

$\{K_1, K_2, K_3, ..., K_n, ...\}$

So we have shown that the squares of the numbers produced by the Babylonian Method converge to $S$.

Proof when $x_1^2 < a$

Let $K$ denote $(a + x_1^2)/2x_1$. We know by the LFT theory that the square of this number is greater than $a$. So, the proof given above can now be applied, by simply 'throwing out' the first number $x_1$ of the sequence.

0

For b):

Consider the function,

$F(x) = 1 + 1/x$.

If you set $F(x)$ to the identity function $x$ and solve for $x$ using the quadratic formula, you will see that $F(x)$ has two fixed points, one positive and one negative.

With a little thought you might guess that our sequence is converging to the positive fixed point,

$\alpha=\frac{1+\sqrt5}{2}$.

Notice that we can restrict the domain of $F(x)$ and analyze the decreasing function

$F: [1.5,\, 2] \to [1.5,\, 2]$

Let $u$ and $v$ be any two distinct points in the closed interval $[1.5,\, 2]$.

Then

$\frac{(F(v) - F(u))}{(v - u)}$

is equal to (algebra)

$\frac {-1}{uv}$

The absolute value of this number can be no larger than

$\frac {1}{1.5*1.5}$, which is equal to $\frac {4}{9}$.

Applying the Banach Fixed Point Theorem,

we see that our sequence $x_{n+1}= 1 + \frac 1 {x_n} (n \in \mathbb N^*), x_1=1$ converges to $\alpha$, since $F(x_1)$ is 2.

Addendum

Actually, for our situation, we don't have to use Banach's theorem. One can easily prove the following, which can also be used to prove convergence of our sequence $x_1, x_2, x_3, ...,$.

Proposition: Let $f(x)$ be a continuous strictly monotonic function mapping a closed interval

$I = [a,\, b]$

into itself.

Assume that there is exactly one fixed point $c$ for $f$ with $a < c < b$.

Then for all $n > 0$, $f^n(I)$ is a closed interval that contains $c$, with $c$ not an endpoint.

Suppose also there is positive $\lambda < 1$, such that for any $\alpha$ $\beta$ with $a < \alpha < \beta < b$, the absolute value of

$\frac{(f(\beta) - f(\alpha))}{(\beta - \alpha)}$

is less than $\lambda$.

Then the intersection, $\cap \, f^n(I) \, | \, n > 0$, contains only one point, $c$.