Show that ${\{x_n}\}$ is convergent and monotone

Question: For $c>0$, consider the quadratic equation $$x^2-x-c=0,\qquad x>0.$$ Define the sequence $\{x_n\}$ recersively by fixing $x_1>0$ 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.

My uncompleted solution: General speaking, the sequence ${\{x_{n+1}}\}$ is a subsequence of ${\{x_n}\}$. Hence, if $\lim_{n \to \infty} x_n = x_s$, then $\lim_{n \to \infty} x_{n+1} = x_s$ as well. So, from sum and productproperties of convergent sequences, (finally) it follows that $x_s=\sqrt{c+x_s}$ which is equivalent to the mentioned quadratic equation for $x>0$. To show that ${\{x_n}\}$ is monotone, it is enough to show that it is bounded, since ${\{x_n}\}$ is convergent. But I don't know how to show that ${\{x_n}\}$ is bounded.

Thank you in advance for a clear guidance/solution.

EDIT : (by considering first two comments to this question, so) The question is, show that ${\{x_n}\}$ is $1-$ convergent, and, $2-$ monotone.

• How do you know that $x_n$ is convergent? You only have proved that if it converges, the limit is a solution of the equation. – Julián Aguirre Jan 30 '15 at 11:49
• "To show that ${\{x_n}\}$ is monotone, it is enough to show that it is bounded, since ${\{x_n}\}$ is convergent", no, that's not enough. – Git Gud Jan 30 '15 at 11:52
• @ Julián Aguirre : Yes really, I didn't considered it. I don't know how to show it's convergent by ϵ−N definition. It doesn't seems be simple, though. – L.G. Jan 30 '15 at 12:10
• @ Git Gud : Yes, you are right. If ${\{x_n}\}$ is convergent then it is bounded; if ${\{x_n}\}$ bounded and monotone then it is convergent. – L.G. Jan 30 '15 at 12:33
• Why do you have to use monotonicity to prove the convergence? – Mhenni Benghorbal Jan 30 '15 at 12:52

Let $f(x)=\sqrt{c+x}$, $x>0$. There is a unique fixed point $x^*$ such that $f(x^*)=x^*$. $x^*$ is in fact the positive solution of $x^2-x-c=0$. The sequence $x_n$ is defined by $x_{n+1}=f(x_n)$.

If $0<x<x^*$, then $x<f(x)<x^*$. From this it is easy to show that if $0<x_1<x^*$ then $x_n$ is increasing and bounded above by $x^*$. This implies that $x_n$ converges and the limit is $x^*$.

If $x^*<x$ then $f(x)>x>x^*$. From this it is easy to show that if $x_1>x^*$ then $x_n$ is decreasing and bounded below by $x^*$. This implies that $x_n$ converges and the limit is $x^*$.

If $x_1=x^*$, then $x_n=x^*$ for all $n$.

• "If $0<x<x^*$, then $x<f(x)<x^*$", why? – L.G. Jan 30 '15 at 21:51
• Look at the graph of the functions. – Julián Aguirre Jan 30 '15 at 23:10
• I am afraid but I can't understand; in the $3^{rd}$ paragraph you wrote $f(x)>x$ (means $x_{n+1}>x_n$) and then you wrote $x_n$ is decreasing (means $x_{n+1}<x_n$). Also, we know that IF ${\{x_n}\}$ converges it will converge to $x^*=0.5+\sqrt{0.25+c}$; by supposing $x>0$. According to the last paragraph of your answer, if, for example, $x_1=x^*$ then $x_2=x^*$ which means $\sqrt {c+0.5+\sqrt{0.25+c}}=0.5+\sqrt{0.25+c}$, which is correct. But to prove that in general? Firstly, graph includes many example but not a proof; secondly,... – L.G. Jan 31 '15 at 3:04
• ... I don't know which graph I have to evaluate, $\sqrt{x+c}$'s output comes back again to x-axis, very complicated to analyze! Is there another way to solve this problem, since it is an end-exercise after topics like "The Sequential Compactness Theorem " and "The Nested Interval Theorem"? Thank you. – L.G. Jan 31 '15 at 3:04
• Draw the graph of $x$ and $\sqrt{c+x}$. The last one is just an increasing curve starting at the point $(0,\sqrt c)$ that cuts the graph of $x$ in one point. – Julián Aguirre Jan 31 '15 at 6:05