Vtyjkyuk

(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 = sqrtc+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.

Assuming that you know that a monotone, bounded sequence converges, you want to do two things. First, show that $langle x_n:ninmathbbZ^+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+sqrt1+4c)$, which I’ll denote by $r$. If $x_nto 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:ninmathbbZ^+rangle$ is both monotone and bounded and hence that it has a limit.

Suppose that $0le 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+1ge r$? That would require that $x_n+1^2-x_n+1-cge 0$ (why?) and hence that $$x_n+1^2ge x_n+1+c>x_n+c=x_n+1^2;,$$ which is clearly impossible. Thus, if $0le 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)=sqrtc+x$; clearly $f$ is continuous, so if the sequence converges to $L$, we have $$L=lim_ntoinftyx_n=lim_ntoinftyx_n+1=lim_ntoinftyf(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_1ge -c$, so that $x_2$ is defined, since $x_2=sqrtc+x_1ge 0$ automatically.

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=sqrtc+L$. There is only one such solution: $L=k$.

Let $r=frac 1+sqrt 1+4c2$ be the positive root of the quadratic, so that $r^2=r+c$ and $rgt 1$

Note that for $ngt 1$ we have $x_ngt 0$

Now suppose $rgt 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_ngt 0$$and $$r-x_n+1=frac r-x_nr+x_n+1lt 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 $rlt x_n$ we have $$x_n+1^2-r^2=(c+x_n)-(r+c)=x_n-rgt 0$$and $$x_n+1-r=frac x_n-rx_n+1+rlt 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.