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.

(Fitzpatrick Advanced Calculus 2e, Sec. 2.4 #12)

For $c \gt 0$, consider the quadratic equation $x^2 - x - c = 0, x > 0$.

Define the sequence $\{x_n\}$ recursively by fixing $|x_1| \lt c$ and then, if $n$ is an index for which $x_n$ has been defined, defining

$$x_{n+1} = \sqrt{c+x_n}$$

Prove that the sequence $\{x_n\}$ converges monotonically to the solution of the above equation.

Note: The answers below might assume $x_1 \gt 0$, but they still work, as we have $x_3 \gt 0$.


This is being repurposed in an effort to cut down on duplicates, see here: Coping with abstract duplicate questions.

and here: List of abstract duplicates.

share|improve this question
    
I have noted that the recursive definition of $\{x_n\}$ is identical to the first equation if $x_{n+1} = x_n$, so is it sufficient to show that $\{x_n\}$ is monotonic and that $x_{n+1}$ converges to $x_n$? And how would I go about doing this? –  cnuulhu Mar 2 '12 at 0:32
    
Clearly a solution of that equation would be a fixed point of $x\mapsto \sqrt{c+x}$. So I'd look at criteria for when a fixed point is attractive. –  Michael Hardy Mar 2 '12 at 0:39
1  
What do you mean by ‘$x_{n+1}$ converges to $x_n$’? –  Brian M. Scott Mar 2 '12 at 0:49
    
Sorry, that wasn't remotely clear. I mean, $\lim_{n \to \infty}|x_{n+1}-x_n| = 0$ –  cnuulhu Mar 2 '12 at 0:59
1  
I guessed that that was what you meant, but I figured that it was best to be sure. You’ve the right feel for what’s going on, but the details take a bit of work: see my answer. (By the way, it would be better to edit your question to include the information in your first comment, so as to make it self-contained.) –  Brian M. Scott Mar 2 '12 at 1:20

3 Answers 3

up vote 7 down vote accepted

Assuming that you know that a monotone, bounded sequence converges, you want to do two things. First, show that $\langle x_n:n\in\mathbb{Z}^+\rangle$ is monotone and bounded, and then show that its limit is the positive root of $x^2-x-c=0$.

If $c=x_1=1$, $x_2=\sqrt2>x_1$, while if $c=1$ and $x_1=2$, $x_2=\sqrt3<x_1$, so if the sequence is monotonic, the direction in which it’s monotonic must depend on $c$ and $x_1$. A good first step would be to try to figure out how this dependence works.

The positive root of the quadratic is $\frac12(1+\sqrt{1+4c})$, which I’ll denote by $r$. If $x_n\to r$, as claimed, and does so monotonically, it must be the case that the sequence increases monotonically if $x_1<r$ and decreases monotonically if $x_1>r$. In the examples in the last paragraph, $r=\frac12(1+\sqrt5)\approx 1.618$, so they behave as predicted.

This suggests that your first step should be to show that if $x_n<r$, then $x_n<x_{n+1}<r$, while if $x_n>r$, $x_n>x_{n+1}>r$; that would be enough to show that $\langle x_n:n\in\mathbb{Z}^+\rangle$ is both monotone and bounded and hence that it has a limit.

Suppose that $0\le x_n<r$; you can easily check that $x_n^2-x_n-c<0$, i.e., that $x_n^2<x_n+c$. On the other hand, $x_{n+1}^2=c+x_n$, so $x_{n+1}^2>x_n^2$, and therefore $x_{n+1}>x_n$. Is it possible that $x_{n+1}\ge r$? That would require that $x_{n+1}^2-x_{n+1}-c\ge 0$ (why?) and hence that $$x_{n+1}^2\ge x_{n+1}+c>x_n+c=x_{n+1}^2\;,$$ which is clearly impossible. Thus, if $0\le x_n<r$, we must have $x_n<x_{n+1}<r$, as desired. I leave the case $x_n>r$ to you.

Once this is done, you still have to show that the limit of the sequence really is $r$. Let $f(x)=\sqrt{c+x}$; clearly $f$ is continuous, so if the sequence converges to $L$, we have $$L=\lim_{n\to\infty}x_n=\lim_{n\to\infty}x_{n+1}=\lim_{n\to\infty}f(x_n)=f(L)\;,$$ and from there it’s trivial to check that $L=r$.

Added: Note that although the problem gave us $x_1>0$, this isn’t actually necessary: all that’s needed is that $x_1\ge -c$, so that $x_2$ is defined, since $x_2=\sqrt{c+x_1}\ge 0$ automatically.

share|improve this answer
    
If possible, can you also edit your answer to include the case $-c \le x_n \le 0$ (if not already sufficient)? –  Aryabhata Mar 2 '12 at 1:48
    
@Aryabhata: That case never arises: we’re given that $c$ and $x_1$ are positive. –  Brian M. Scott Mar 2 '12 at 1:54
    
I know. I just want the answer to cater to the case when $x_1 \lt 0$. I am trying to get this to be one of the abstract parents. See my edits to the question. So it would be great if you can do it (if not, I will edit your answer later). (It is a simple noting that $x_2 \gt 0$ and rest of the argument works, I suppose) –  Aryabhata Mar 2 '12 at 1:56
    
@Aryabhata: Now I understand. Done. –  Brian M. Scott Mar 2 '12 at 2:18
    
Thank you......! –  Aryabhata Mar 2 '12 at 2:27

Let $k$ be the positive root to your polynomial. Note that $y=x^2-x-c$ is an upward opening parabola with its vertex below the $x$-axis and an initial downward slope. This implies that positive $x$-values less than $k$ produce negative output, while $x$-values greater than $k$ produce positive output.

Note also that all $x_n$ are positive, so it will be acceptable to preserve equalities and inequalities involving $x_n^2$ after taking a square root.

If $x_0=k$, then $x_1^2=c+k=k^2$, so $x_1=k$. The sequence continues like this, and is constant.

If $x_n<k$, then $x_{n+1}^2=c+x_n<c+k=k^2$. So $x_{n+1}<k$. (Similarly if $x_n>k$, then $x_{n+1}>k$.) This establishes that the sequence is either bounded above or below, depending on where $x_0$ is in relation to $k$.

If $x_n<k$, then $x$ is a positive number to the left of the root of your polynomial. $x$-values in this region produce negative output, so $x_n^2-x_n-c<0$. That implies that $x_{n+1}^2=c+x_n>x_n^2$, and so $x_{n+1}>x_n$. (Similarly if $x_n>k$, then $x_{n+1}<x_n$.)

Thus if $x_0<k$ you will have an increasing sequence bounded above. And if $x_0>k$ you will have a decreasing sequence bounded below.

So the limit exists under all possible cases. It's value has to be a solution to $L=\sqrt{c+L}$. There is only one such solution: $L=k$.

share|improve this answer

Let $r=\frac {1+\sqrt {1+4c}}2$ be the positive root of the quadratic, so that $r^2=r+c$ and $r\gt 1$

Note that for $n\gt 1$ we have $x_n\gt 0$

Now suppose $r\gt x_n$ so with $x_{n+1}^2=c+x_n$ we have $$r^2-x_{n+1}^2=(r+c)-(c+x_n)=r-x_n\gt 0$$and $$r-x_{n+1}=\frac {r-x_n}{r+x_{n+1}}\lt r-x_n$$

Whence $x_n$ is monotonically increasing, and getting closer to $r$ - the difference reduces at least as fast as $r^{-n}$, so the limit is easy to prove.

On the other hand if $r\lt x_n$ we have $$x_{n+1}^2-r^2=(c+x_n)-(r+c)=x_n-r\gt 0$$and $$x_{n+1}-r=\frac {x_n-r}{x_{n+1}+r}\lt x_n-r$$and the sequence is decreasing and bounded below by $r$, and it is once again easy to prove that this is the limit.

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.