# Show that the sequence defined as $x_{n+1}=\sqrt{x_n+x_{n-1}}$ converges

Show that the sequence $$(x_n)$$ defined as $$x_{n+1}=\sqrt{x_n+x_{n-1}}, x_0=3,x_1=2$$ converges. Here i wil try to prove that $$(x_n)$$ converges considering all details. So. i would like to have a critical feedback on my proof and would like to know if i missed something or did much more than it should be.. Here $$\mathbf{R}^*$$ will denote $$\mathbf{R}\ \ \not \ \{0\}$$.

Consider a function $$f(x)=\sqrt{x}$$. First, we show that it's defined on $$\mathbf{R}$$ and then we will show that $$f(x)$$ is an increasing function on $$\mathbf{R}$$.

We remark that $$f(x)$$ is differntiable on $$\mathbf{R}^*$$. Let $$a \in \mathbf{R}^*$$. By definition of differentiable function the $$\lim_{x\to a}\frac{f(x)-f(a)}{x-a}$$ msut exist:

$$\lim_{x\to a}\frac{f(x)-f(a)}{x-a}=\frac{1}{3\sqrt{a^2}}$$ and so it exists $$\forall a \in \mathbf{R}^*$$ as we chose an arbitrary $$a$$. So $$f(x)$$ is differentiable on $$\mathbf{R}^*$$ and so is continious on $$\mathbf{R}^*$$.

We show now that $$f(x)$$ is continious on $$0$$. To show that we pass by the definition :

$$\forall \varepsilon>0 \ \exists \delta>0 \ \forall x \in \mathbf{R}$$: $$|x|<\delta \implies |f(x)|=|\sqrt{x}|<\varepsilon$$

To satisfy the definition, one can take $$\delta=\varepsilon^3$$, so it holds and we can conclude that $$f(x)$$ is continious on $$\mathbf{R}$$.

Let $$a,b \in \mathbf{R}$$ such that $$a. As $$f(x)$$ is continious on $$\mathbf{R}$$ we can write:

$$a

As $$a,b$$ are arbitrary numbers (satisfying $$a), we can conclude that $$f(x)$$ is strictly incrasing function.

Now, as all preliminary results are proven, we can show that $$(x_n)$$ is a convergent sequence. For that, we show that $$(x_n)$$ is monotonic and bounded.

$$\bullet$$ $$(x_n)$$ is decreasing: Suppose $$x_{n+1}. The previous inequality holds for $$n=1$$ so we can suppose that it works up to a certain $$n\in \mathbf{N}^*$$. We show nowthat it holds for $$n+1$$:

$$x_{n+2}. But, as $$f(x)=\sqrt{x}$$ is strictly increasing function and by induction hypothesis $$x_{n+1}, we can conclude that $$x_{n+2} and so $$x_{n+1} holds $$\forall n\in\mathbf{N}^*$$. So $$(x_n)$$ is decreasing.

$$\bullet$$ $$(x_n)$$ is bounded below: Suppose $$x_n>1$$. It holds for $$n=1$$ so we can suppose that it works up to a certain $$n\in \mathbf{N}^*$$. We want to show now that t holds for $$n+1$$:

$$x_{n+1}>1 \iff \underbrace{x_{n}}_{>1}+\underbrace{x_{n-1}}_{>1}>1$$ which is true, because $$(x_n)$$ is decreasing. So we conclude that $$x_n>1 \ \forall n\in \mathbf{N}^*$$.

So, we have shown that $$(x_n)$$ converges.

• I just have a question: i also could have shown that $(x_n)$ is bounded below by 0. But, if i calculate the limit (solving an equation), i have 3 different values: $L=0,L=\sqrt{2}$. We can drop the solution $"-"\sqrt{2}$ but how can i be sure that it is $"+"\sqrt{2}$ and not 0 in my case? It is kinda immediat if i calculate first 5-6 values of the sequence, but still i would like to know how to be sure for 100% and have a rigorous proof. Feb 14, 2021 at 17:34
• The query's title indicates that it is sufficient to determine that the sequence is convergent - calculating the actual limit of the sequence is therefore irrelevant. Consequently, all that is required is that  the sequence is strictly decreasing and  there exists some lower bound for the sequence (regardless of what that lower bound is). From this perspective, a lower bound of $0$ works fine. Feb 14, 2021 at 17:41
• @user2661923 Yes, it wasn't asked to calculate a limit but still by curioisty why couldn't I ask this question... Feb 14, 2021 at 17:42
• Assuming that it is established that the sequence is strictly decreasing and (therefore) converges to some non-negative value $L$, one approach is to recognize that the $\lim_{n\to\infty} x_n = L = \lim_{n\to\infty} \left(x_{(n-1)} + x_n\right)^{(1/3)}.$ Another approach is to guess the value of $L$, show that $\forall n, x_n > L$, and further show that the assumption that the limit equals some other value $L_1 > L$ leads to a contradiction. Feb 14, 2021 at 17:51
• My bad, I didn't actually scrutinize your analysis. If you have analysis that demonstrates that there is a finite set $S$ such that $L$ must be an element of $S$, then yes, one way of completing the problem is to prove that there is only 1 value (i.e. element) in the set $S$ that will work. Feb 14, 2021 at 18:19

$$x_{n+1}=\sqrt{x_{n}+x_{n-1}};\;x_0=3;\;x_1=2$$ $$(x_n)$$ is a decreasing sequence

Proof. (by strong induction)

for $$n=1$$

$$x_2=\sqrt{x_0+x_1}=\sqrt{5}

Now suppose that it is true for all integers $$1,2,\ldots, n$$, and let's prove it for $$(n+1)$$

$$x_{n+2}=\sqrt{x_{n+1}+x_{n}}$$

$$x_{n+2}^3=x_{n+1}+x_n thus $$x_{n+2}. Proved.

The sequence is decreasing and is bounded above by $$x_n\le 3$$

$$x_n>1$$ for any $$n$$.

$$x_1=2>1$$. Suppose $$x_n>1$$ for $$0,1,2,\ldots,n$$.

$$x_{n+1}=\sqrt{x_n+x_{n+1}}>\sqrt{1+1}>1$$. Proved.

Thus the sequence is bounded above and below $$1, therefore it converges

$$x_n\to x$$ as $$n\to\infty$$

To find the limit let's use the definition

$$x=\sqrt{x+x}\to x^3=2x\to x=\sqrt 2$$

The sequence converges to $$\sqrt 2$$.

• @archuser The fact that $f(x)=\sqrt{x}$ is strictly increasing is common knowledge. The feedback on your proof is implicit in my answer's length: 8 lines vs 33. Feb 14, 2021 at 21:20
• @archuser Your proof is verbose. You prove that $\sqrt{x}$ is continuous, that $x^3$ is increasing. You even compute the derivative from the definition! The inferior bound is trivially zero... as user2661923 commented three hours ago. My feeling is that you confused rigorous with pedantic Feb 14, 2021 at 21:37
• @archuser were you looking for feedback or for unconditionally praise? Feb 14, 2021 at 21:44
• @Raffaele: Your $x$ could be $0$ why not ?. You still have to “show” that $x > 0$. ! Feb 14, 2021 at 21:55
• @DeepSea You are right! Feb 14, 2021 at 22:02

• To prove $$f$$ is continuous, you say that it's differentiable. But you do not prove that $$f$$ is differentiable directly - you only state the derivative. You could show that the derivative exists with this value, but that proof would be very similar to proving $$f$$ is continuous directly (e.g. using the binomial theorem). So it would be simpler to just do that.
• To prove $$f$$ is increasing, you just say "$$f$$ is continuous, therefore [$$f$$ is increasing]". There is no proof in your question that $$f(x) = \sqrt{x}$$ is an increasing function.
• Your proofs that $$(x_{n})$$ is decreasing and bounded below by 1 appear to be correct. Note that they only rely on the fact that $$f$$ is increasing and that $$f(1) = 1$$. You haven't used the fact that $$f$$ is continuous anywhere.
• However, the property that $$f$$ is continuous does allow you to find the limit. In general, if $$x_n \to x$$ and $$f$$ is continuous, then $$f(x_n) \to f(x)$$. Applying this to the equation $$x_{n+1} = f(x_n+x_{n-1})$$ shows that the limit satisfies $$x = f(2x)$$. In other words, $$x^3 = 2x$$, so either $$x=0$$, $$x=-\sqrt{2}$$ or $$x=\sqrt{2}$$. But since you argued already that $$x > 1$$, the limit must be $$\sqrt{2}$$.
After showing that the limit exists and call it $$x$$. We show next that: $$x \ge \sqrt{2}$$. Using the decreasing property just established we have: $$x_n = \sqrt{x_{n-1} + x_{n-2}} > \sqrt{2x_n} \implies x_n^3 > 2x_n \implies x_n(x_n^ 2 - 2) > 0 \implies x_n > \sqrt{2}, \forall n \ge 1 \implies x \ge \sqrt{2} \implies x = \sqrt{2}$$, because it’s shown that $$x = 0$$ or $$x = \sqrt{2}$$.