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.

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!

share|improve this question
1  
This link might be useful for a: proofwiki.org/wiki/… –  Martin Sleziak Nov 17 '11 at 20:26
    
oops martin, sorry, you're right! –  Clash Nov 17 '11 at 20:33
    
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. 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. –  Martin Sleziak Nov 17 '11 at 21:01

5 Answers 5

up vote 12 down vote accepted

(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<x_3<x_5$, 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<x_3<x_5<\dots <x<\dots<x_6<x_4<x_2\;.$$

If you can show that $x_{2n+1}<x_{2n+3}<x_2$ 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<x_{2n+2}<x_{2n}$ 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}<x_{n+2}&\text{ iff } \frac{5x_n+3}{3x_n+2}<\frac{2x_n+1}{x_n+1}\\ &\text{ iff }5x_n^2+8x_n+3<6x_n^2+7x_n+2\\ &\text{ iff }0<x_n^2-x_n-1\\ &\text{ iff }2x_n+1<x_n^2+x_n\\ &\text{ iff }x_{n+2}<x_n \end{align*}\tag{1}$$

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<x_3<x_5<\dots <\varphi<\dots<x_6<x_4<x_2\;.$$ 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}$.

share|improve this answer
    
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? –  Clash Nov 16 '11 at 15:05
    
@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$, and 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}<x_n$, then $x_{n+4}<x_{n+2}$, and similarly for $>$. –  Brian M. Scott Nov 16 '11 at 15:23
    
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. –  Clash Nov 16 '11 at 15:52
    
So, $x_{n+2} > x_n$ until $x_n < \varphi = \frac12(1+\sqrt 5)$? –  Clash Nov 16 '11 at 15:54
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_1<x_3$, the fact that the odd-numbered terms are increasing follows by induction. Now do the same thing with $<$ and the even-numbered terms. –  Brian M. Scott Nov 16 '11 at 16:09

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
what's AM and GM? –  Clash Nov 17 '11 at 18:36
    
@Clash en.wikipedia.org/wiki/… –  pharmine Nov 18 '11 at 3:16

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

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.