15
$\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!

  • 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_1, and $x_2>x_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} for all $n\ge 0$, you’ll know that the sequence of odd-numbered is monotone increasing and bounded above, which implies that it converges to some $x_{\text{odd}}$. Similarly, if you can show that $x_1 for every $n\ge 1$, you’ll know that the sequence of even-numbered terms is monotone decreasing and bounded below, which implies that it converges to some $x_{\text{even}}$. Then you’ll have to find a way to show that $x_{\text{odd}}=x_{\text{even}}$.

(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_1 In particular, the sequence of odd-numbered terms is increasing and bounded above by $\varphi$, and the sequence of even-numbered terms is decreasing and bounded below by $\varphi$, so both have limits. This doesn’t yet prove that both subsequences have the same 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
    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
12

(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.)

6

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
    @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
    @Clash http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means2011-11-18
2

Following robjohn note that $x_{n+1} \le x_n$ and by AM-GM inequality, $$|x_{n+1}|=\frac{1}{2}\lvert x_n+\dfrac{a}{x_n}\rvert \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.$

1

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$.